编辑代码

#include <iostream>
using namespace std;


//合并
bool merge(int arr[],int arrStart,int mid,int arrEnd){
    int i=arrStart;
    int j=mid;
    int arrLen=arrEnd-arrStart;

    if(arrLen<2){
        return false;
    }

    int *temp=new int(arrEnd-arrStart);
    int tempIndex=0;

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

    while(i<mid){
        temp[tempIndex++]=arr[i++];
        //temp[tempIndex]=arr[i];
        //++tempIndex;
        //++i;
    }

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

    for(int index=0;index<arrEnd-arrStart;++index){
        arr[arrStart+index]=temp[index];
    }

    delete temp;
    return true;
}


//arrEnd=arr.length 是数组最后一个元素的下标+1
//分解
bool mergeSort(int arr[],int arrStart,int arrEnd){
    int arrLen=arrEnd-arrStart;

    if (arrLen < 1) {
        return false;
    }

    if(arrLen==1){
        return true;
    }

    int mid=arrStart+arrLen/2;

    mergeSort(arr,arrStart,mid);
    mergeSort(arr,mid,arrEnd);

    return merge(arr,arrStart,mid,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 = 0;

    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);


}