归并排序 时间复杂度：O(n·logn)； 空间复杂度：O(n) 稳定排序 分治法： 1.分解 2.解决 3.合并

MergeSort.c

// 归并排序 arr带排序的数组 ，p开始index，q为中间切割index，r为数组末尾index
void mergeSortUnit(int *arr,int p,int q, int r) {
    int n1 = q-p+1; // 子数组1的个数n1
    int n2 = r-q; // 子数组2的个数n2
	 // 最后一位用来存饭哨岗值正无穷大
    int *leftArr = malloc((n1+1) * sizeof(int)); 
    for (int i = 0; i < n1; i++) {
        leftArr[i] = arr[p + i];
    }
    int *rightArr = malloc((n2+1) * sizeof(int));
    for (int i = 0; i < n2; i++) {
        rightArr[i] = arr[q+i+1];
    }
    // 最后一位用来存饭哨岗值正无穷大
    leftArr[n1] = INT_MAX;
    rightArr[n2] = INT_MAX;
    int i = 0;
    int j = 0;
    for (int k = p; k <= r; k++) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k] = leftArr[i];
            i += 1;
        } else {
            arr[k] = rightArr[j];
            j += 1;
        }
    }
}

void mergeSort(int *arr,int p,int r) {
    if (p >= r) { // 数组只有一个元素
        return;
    }
    int q = (p + r) / 2;
    mergeSort(arr, p, q);
    mergeSort(arr, q+1, r);
    mergeSortUnit(arr, p, q, r);
}
// 测试用例
int arr[] = {5,2,7,4,1,2,3,6};
int count = 8;
mergeSort(arr, 0, count-1);
for (int i = 0; i < count; i++) {
    NSLog(@"i:%d,arr[i]:%d",i,arr[i]);
}