objectiv

时间复杂度：O(n log n)

代码：

- (NSArray *)mergeSort:(NSArray *)array {

NSMutableArray *tmpArray = [[NSMutableArrayalloc] init];

for(inti =0; i < array.count; i++) {

NSMutableArray *subArray = [[NSMutableArrayalloc] init];

[subArray addObject:array[i]];

[tmpArray addObject:subArray];

}

while(tmpArray.count != 1) {

NSUIntegerj = 0;

while(j < tmpArray.count-1) {

tmpArray[j] = [self mergeSortedArray:tmpArray[j] secondArray:tmpArray[j +1]];

[tmpArray removeObjectAtIndex:j +1];

j ++;

}

}

returnt mpArray.firstObject;

}

- (NSArray *)mergeSortedArray:(NSArray *)firstArray secondArray:(NSArray *)secondArray {

NSMutableArray *resultArray = [[NSMutableArrayalloc] init];

NSUInteger firstIndex =0;

NSUInteger secondIndex =0;

while(firstIndex < firstArray.count && secondIndex < secondArray.count) {

if(firstArray[firstIndex] < secondArray[secondIndex]) {

[resultArray addObject:firstArray[firstIndex]];

firstIndex ++;

}else{

[resultArray addObject:secondArray[secondIndex]];

secondIndex ++;

}

}

while(firstIndex < firstArray.count) {

[resultArray addObject:firstArray[firstIndex]];

firstIndex ++;

}

while(secondIndex < secondArray.count) {

[resultArray addObject:secondArray[secondIndex]];

secondIndex ++;

}

return resultArray;

}