归并排序

/**

算法思想：

把长度为n的输入序列分成两个长度为n/2的子序列；

对这两个子序列分别采用归并排序；

将两个排序好的子序列合并成一个最终的 排序 序列。

O(n log n）的时间复杂度。代价是需要额外的内存空间。

*/

/**

归并排序--将两段排序好的数组结合成一个排序数组

@param leftArray leftArray

@param rightArray rightArray

@return NSArray

*/

NSArray *merger(NSArray *leftArray, NSArray *rightArray) {
    NSUInteger capacity = leftArray.count+rightArray.count;
    NSMutableArray *arrayM = [NSMutableArray arrayWithCapacity:capacity];
    for (NSInteger index=0, i = 0, j=0; index < capacity; index++) {
        if (i>=leftArray.count) {
            arrayM[index] = rightArray[j++];
        } else if (j >= rightArray.count) {
            arrayM[index] = leftArray[i++];
        } else if (leftArray[i] > rightArray[j]) {
            arrayM[index] = rightArray[j++];
        } else {
            arrayM[index] = leftArray[i++];
        }
    }
    return arrayM.copy;
}

/**

归并排序

@param array array

@return 返回排序好的数组

*/

NSArray *mergerSort(NSArray *array){
    if (array.count<2) {
        return array;
    }
    NSUInteger count = array.count;
    NSUInteger mid =array.count/2;
    NSArray *leftArray = [array subarrayWithRange:NSMakeRange(0, mid)];
    NSArray *rightArray = [array subarrayWithRange:NSMakeRange(mid, count-mid)];
    return merger(mergerSort(leftArray), mergerSort(rightArray));
}