编辑代码

#include <iostream>
#include <math.h>

using namespace std;

// 归并排序的核心思想是不断把无序数组进行切分左右两个长度基本相等的数组，直至切分的数组里面的数据个数为1，
// 此时可以认为这个只有一个数据的数组就是有序的
// 然后将切分后的左右两个有序数组进行合并，两个合并后的有序数据就是有序的，
// 再继续将合并后的左右两个的有序数组合并，直至将整个数组合并完成，这个数组就有序了
bool merge(int array[], size_t arrStart, size_t arrMiddle, size_t arrEnd) {
    int arrLen = arrEnd - arrStart;
    if (arrLen < 2) {
        cout << "Please check your implementation." << endl;
        return false;
    }

    int *temp = new int(arrLen);
    int i = arrStart;
    int j = arrMiddle;
    int tempIndex = 0;

    while (i < arrMiddle && j < arrEnd) {
        if (array[i] > array[j]) {
            temp[tempIndex] = array[j];
            ++j;
        }
        else {
            temp[tempIndex] = array[i];
            ++i;
        }
        ++tempIndex;
    }

    // 小数组有剩余数据
    while (i < arrMiddle) {
        temp[tempIndex++] = array[i++];
    }

    while (j < arrEnd) {
        temp[tempIndex++] = array[j++];
    }

    // 把排好序的数据拷贝回去
    for ((tempIndex = 0, i = arrStart); (tempIndex < arrLen && i < arrEnd); (++tempIndex, ++i)) {
        array[i] = temp[tempIndex];
    }

    delete []temp;
    temp = NULL;

    return true;
// array 需要排序的数组
// arrStart 数组起始位置的下标
// arrEnd数组终止位置的下标+1
bool mergeSort(int array[], size_t arrStart, size_t arrEnd) {
    int arrLen = arrEnd - arrStart;
    if (arrLen < 0) {
        cout << "Please check your input." << endl;
        return false;
    }

    // 写终止条件
    if (arrLen == 0 || arrLen == 1) {
        return true;
    } 

    // 把数组平均分成两分
    // floor表示取下整数：2.5的下整数2
    int middle = arrStart + floor(arrLen / 2);

    mergeSort(array, arrStart, middle);
    mergeSort(array, middle, arrEnd);
    // 合并
    return merge(array, arrStart, middle, arrEnd);
}

void printArray(int array[], int arrLen) {
    for (int i = 0; i < arrLen; ++i) {
        cout << array[i] << " ";
    }
    cout << endl;
}

int main(){
    int array0[] = {};
    int arrayLen = sizeof(array0)/sizeof(int);

    printArray(array0, arrayLen);
    mergeSort(array0, 0, arrayLen);
    printArray(array0, arrayLen);

    cout << "=========================================" << endl;

    int array1[] = {1};
    arrayLen = sizeof(array1)/sizeof(int);

    printArray(array1, arrayLen);
    mergeSort(array1, 0, arrayLen);
    printArray(array1, arrayLen);

    cout << "=========================================" << endl;

    int array2[] = {2, 1};
    arrayLen = sizeof(array2)/sizeof(int);

    printArray(array2, arrayLen);
    mergeSort(array2, 0, arrayLen);
    printArray(array2, arrayLen);

    cout << "=========================================" << endl;

    int array3[] = {1, 5, 3};
    arrayLen = sizeof(array3)/sizeof(int);

    printArray(array3, arrayLen);
    mergeSort(array3, 0, arrayLen);
    printArray(array3, arrayLen);


    cout << "=========================================" << endl;

    int array4[] = {9, 12, 8, 7};
    arrayLen = sizeof(array4)/sizeof(int);

    printArray(array4, arrayLen);
    mergeSort(array4, 0, arrayLen);
    printArray(array4, arrayLen);

    cout << "=========================================" << endl;

    int array5[] = {9, 12, 8, 7, 3};
    arrayLen = sizeof(array5)/sizeof(int);

    printArray(array5, arrayLen);
    mergeSort(array5, 0, arrayLen);
    printArray(array5, arrayLen);


}