归并排序（递归）

void _MergeSort(int* arr, int begin, int end, int* tmp) { // [begin, end]
    if(begin >= end) { // 保证至少有两个元素，才需要排序。一个即为有序。
        return;
    }
    int mid = (begin+end)/2;
    // 这里的操作是将左右子区间变为有序。
    // [begin, mid] [mid+1, end] 分治递归，让子区间有序。
    _MergeSort(arr, begin, mid, tmp);
    _MergeSort(arr, mid+1, end, tmp);
    // 归并，arr中左右子区间有序了，归并到tmp中对应位置，再拷贝回来。
    int begin1 = begin, end1 = mid;
    int begin2 = mid+1, end2 = end;
    int index = begin;
    while(begin1 <= end1 && begin2 <= end2) {
        if(arr[begin1] < arr[begin2]) {
            tmp[index++] = arr[begin1++];
        }else {
            tmp[index++] = arr[begin2++];
        }
    }
    while(begin1 <= end1) {
        tmp[index++] = arr[begin1++];
    }
    while(begin2 <= end2) {
        tmp[index++] = arr[begin2++];
    }
    // 此时，左右子区间合并到了tmp的对应位置上。再拷贝回arr即可
    memcpy(arr+begin, tmp+begin, (end-begin+1)*sizeof(int));
}

void MergeSort(int* arr, int n) {
    int* tmp = (int*)malloc(n*sizeof(int));
    if(tmp == nullptr) {
        cout<<"MergeSort::malloc fail"<<endl;
        exit(-1);
    }
    _MergeSort(arr, 0, n-1, tmp);
    free(tmp);
}

归并排序的大致思想：先使得左右区间有序，如上10 6 7 1 3 9 4 2 使得10 6 7 1 变为1 6 7 10 .? ? ? ? 3 9 4 2 变为2 3 4 9 之后采用O(N)的算法将这两个区间合并到一个tmp临时数组上（对应下方的蓝色数组），这时，在tmp临时数组上是有序的，再拷贝回原数组的对应位置即可。

如何使得左右区间都有序呢？这里就要采用递归的方法。8 -> 4 4? ?4 -> 2 2? ?2 -> 1 1? ?当1 1 时表示这段区间元素个数只有1 直接返回。（其实这里也可以在元素个数为2的函数栈帧内判断左右区间个数，直接不予递归，这样就不会进入函数递归了。否则就是进入函数之后判断区间的元素个数）返回之后，表示元素个数为2的区间左右子区间都有序了，同样采用算法排序合并到tmp的对应位置再拷贝回去。

上方的O(N)算法类似于两个有序链表的合并。整体的思想十分像二叉树的后序遍历，即先将左右子区间有序，再处理整个。而左区间又是先递归左区间的左区间，左区间如果还有左区间就继续递归。再层层返回。约等于二叉树的后序遍历。? ?其实整个算法还是比较简单的。

时间复杂度：严格的O(N* LogN)

空间复杂度：O(N)? ?（O(N+LogN) logn忽略。

稳定性：稳定? （归并，冒泡，插入）

归并排序（非递归）

非递归1

void MergeSortNoRecursion(int* arr, int n) {
    int* tmp = (int*)malloc(n*sizeof(int));
    if(tmp == nullptr) {
        cout<<"MergeSortNoRecursion::malloc fail"<<endl;
        exit(-1);
    }
    int gap = 1;
    while(gap < n) {
        for(int i = 0; i < n; i += 2 * gap) {  // 2*gap是一组排完序的个数，到下一组了。
            // [i, i+gap-1] [i+gap, i+2*gap-1]  对这两个范围内的数据进行排序。
            // begin1=i不可能越界，只有end1，begin2，end2可能越界。
            int begin1 = i, end1 = i + gap - 1;
            int begin2 = i + gap, end2 = i + 2 * gap - 1;

            //越界检查，修改后其实还是基于下面的归并逻辑以及memcpy的位置。
            if(end1 >= n) {
                end1 = n - 1;
                // 右区域数组改为不存在的范围，从而下面的逻辑就只会把[begin1, end1]拷贝到tmp中
                begin2 = n;
                end2 = n-1;
            }else if(begin2 >= n) {
                // 右区域数组越界，只需要把[begin1, end1]拷贝到tmp中即可。
                begin2 = n;
                end2 = n-1;
            }else if(end2 >= n) {
                // 这种情况，比如一共10个元素，此时gap为8，则表示这是最后一次归并
                // 那么只有end2越界，此时需要归并，只是一个不对称的归并而已
                end2 = n-1;
            }

            // 对[i, i+gap-1] [i+gap, i+2*gap-1]范围内进行归并
            int index = begin1;
            while (begin1 <= end1 && begin2 <= end2) {
                if (arr[begin1] < arr[begin2]) {
                    tmp[index++] = arr[begin1++];
                } else {
                    tmp[index++] = arr[begin2++];
                }
            }
            while(begin1 <= end1) {
                tmp[index++] = arr[begin1++];
            }
            while(begin2 <= end2) {
                tmp[index++] = arr[begin2++];
            }
        }
        // 全部归并完，再全部拷贝回去。
        memcpy(arr, tmp, n*sizeof(int));
        gap *= 2;
    }
    free(tmp);
}

非递归的整体思想：可以看递归版归并排序的图，其实可以先11归并，再22归并，再44归并。。。。gap起初为1 表示11归并。不过要注意，上方的这个代码是在循环结束后，也就是每组元素都排序到tmp数组后，再统一拷贝回去。这一点很重要。上方的11合并 22合并 44合并导致一个问题，也就是如果数组元素不是2的次方个，就会导致某次合并时[i, i+gap-1] [ i+gap, i+2*gap-1] 这个范围的后三个点处可能越界。i不会是因为如果i越界就直接退出循环了。而针对这三个点的越界情况，需要进行修正，也就是for循环中开始处的if if else if else。暂且先不思考越界的情况，先说修正方法：当i+gap-1越界时，把i+gap-1改为n-1 后面的范围改为前>后即可，这是因为我们必须把第一个范围中的不越界的元素利用下方的O(N)算法拷贝到tmp数组中，在循环结束后再统一拷贝回去。当第二个范围修改之后，就会使得下方的循环达成不访问第二个范围的目的。可以看代码。

而当end2 >=n时? 我们的修改是因为我们必须要把这两个范围中的元素排序合并到tmp数组中。这时，两个范围中的元素个数并不相等。

非递归2

void MergeSortNoRecursion2(int* arr, int n) {
    int* tmp = (int*)malloc(n*sizeof(int));
    if(tmp == nullptr) {
        cout<<"MergeSortNoRecursion::malloc fail"<<endl;
        exit(-1);
    }
    int gap = 1;
    while(gap < n) {
        for(int i = 0; i < n; i += 2 * gap) {  // 2*gap是一组排完序的个数，到下一组了。
            // [i, i+gap-1] [i+gap, i+2*gap-1]  对这两个范围内的数据进行排序。
            // begin1=i不可能越界，只有end1，begin2，end2可能越界。
            int begin1 = i, end1 = i + gap - 1;
            int begin2 = i + gap, end2 = i + 2 * gap - 1;

            //越界检查，修改后其实还是基于下面的归并逻辑以及memcpy的位置。
            if(end1 >= n) {
                break;
            }else if(begin2 >= n) {
                break;
            }else if(end2 >= n) {
                // 这种情况，比如一共10个元素，此时gap为8，则表示这是最后一次归并
                // 那么只有end2越界，此时需要归并，只是一个不对称的归并而已
                end2 = n-1;
            }
            int copyNum = end2 - begin1 + 1;
            // 对[i, i+gap-1] [i+gap, i+2*gap-1]范围内进行归并
            int index = begin1;
            while (begin1 <= end1 && begin2 <= end2) {
                if (arr[begin1] < arr[begin2]) {
                    tmp[index++] = arr[begin1++];
                } else {
                    tmp[index++] = arr[begin2++];
                }
            }
            while(begin1 <= end1) {
                tmp[index++] = arr[begin1++];
            }
            while(begin2 <= end2) {
                tmp[index++] = arr[begin2++];
            }
            memcpy(arr+i, tmp+i, copyNum*sizeof(int));
        }
        // 全部归并完，再全部拷贝回去。
        gap *= 2;
    }
    free(tmp);
}

这里从tmp数组中拷贝回去的时机改变了，也就使得越界修改的方法改变了。即当end1 或 begin2越界时，可以直接不从arr往tmp中合并，因为此时arr中的元素本身就是正确的。而当end2越界时，需要修正，然后再讲这组元素合并排序到tmp。最后再从tmp中拷贝回这一组。