归并排序(Merge Sort)原理：将当前数组拆分成两个子数组，一直拆分到每个数组只有一个元素再重新依次有序合并的过程。
归并排序(Merge Sort)核心思想：两个有序数组合并为一个有序数组。
- (void)mergeArrayWithBegain:(NSInteger)begain mid:(NSInteger)mid end:(NSInteger)end
{
NSInteger li = 0, le = mid - begain; // 左边的子数组下标
NSInteger ri = mid, re = end; // 右边的子数组下标
NSInteger ai = begain; // 待合并成数组起始下标
// 将左子数组备份
NSMutableArray *mArray = [NSMutableArray array];
for (NSInteger i = li; i < le; i++) {
[mArray addObject:self.sortArray[begain + I]];
}
// 因为左右子数组是有序的，只需要从头开始比较左右子数组即可，哪个小哪个放入数组中，同时下标向后移动一位。
while (li < le) {
if (ri < re && [self compareObjcet:self.sortArray[ri] anotherObject:mArray[li]]) {
self.sortArray[ai++] = self.sortArray[ri++];
} else {
self.sortArray[ai++] = mArray[li++];
}
}
}
至于拆分与合并都是递归调用的过程：
- (void)sortArrayWithBegin:(NSInteger)begain end:(NSInteger)end
{
if (end - begain >= 2) {
NSInteger mid = (begain + end) >> 1;
// 递归拆分左子数组
[self sortArrayWithBegin:begain end:mid];
// 递归拆分右子数组
[self sortArrayWithBegin:mid end:end];
// 合并数组
[self mergeArrayWithBegain:begain mid:mid end:end];
}
}
整体的排序操作其实就是简单的给出最大数组
- (void)sort
{
NSInteger arrayCount = self.sortArray.count;
[self sortArrayWithBegin:0 end:arrayCount];
}
总结：归并排序中无疑用到的就是递归调用。其时间复杂度计算方式 T(n) = 2 * T(n/2) + O(n);最后计算得 T(n) = O(nLogn);
T (n) =2∗T (n/2) +O(n)
T1 =O(1)
T (n) /n =T (n/2) /(n/2)+O(1)
◼令Sn =T(n)/n
S1 =O(1)
S (n) =S (n/2) +O(1)=S (n/4) +O(2)=S (n/8) +O(3)=S (n/2^k) +O(k) =S (1) +O(logn)=O(logn)
T (n) =n∗S (n) =O(nlogn)
同时附上常见的递推式及复杂度对应表：
常见的递推式及复杂度
