归并排序是一种常用的排序算法，其原理是将每一个数看作一个有序序列，然后不断地将两个相邻的有序序列合并成一个有序序列，最后剩下一个有序序列就是排序后的结果。用到的是递归和分治思想。

#include<iostream>
#include<malloc.h>
using namespace std;

void merge(int arr[], int tempArr[], int left, int mid, int right){
    int l_pos = left;   //左半区第一个未排序的元素位置
    int r_pos = mid+1;  //右半区第一个未排序的元素位置
    int pos = left;     //存入临时数组时的元素位置

    //进行归并排序的合并操作
    while(l_pos<=mid && r_pos<=right){
        if(arr[l_pos] < arr[r_pos]){
            tempArr[pos++] = arr[l_pos++];
        }else{
            tempArr[pos++] = arr[r_pos++];
        }
    }

    //左半区有剩余元素
    while(l_pos <= mid){
        tempArr[pos++] = arr[l_pos++];
    }

    //右半区有剩余元素
    while(r_pos <= right){
        tempArr[pos++] = arr[r_pos++];
    }

    //把合并好的临时数组复制回原始数组
    pos = left;
    while(pos <= right){
        arr[pos] = tempArr[pos];
        pos++;
    }
}

void msort(int arr[], int tempArr[], int left, int right){
    
    if(left < right){ // 有两个及以上的元素时进行划分
        int mid = (right + left) / 2;   // 找到中间的位置

        msort(arr, tempArr, left, mid); // 递归划分arr数组的左半部分

        msort(arr, tempArr, mid+1, right);  // 递归划分arr数组的右半部分

        merge(arr, tempArr, left, mid, right);  // 合并已经排序的部分

    }
}

// 归并排序入口
void MergeSort(int arr[], int n){
    // 进行归并排序的原始数组arr， 数组长度n

    // 申请相同长度的临时数组空间
    int *tempArr = (int*)malloc(n * sizeof(int));
    if(tempArr){
        cout << "Allocate Memory successfully" << endl;
        msort(arr, tempArr, 0, n-1);
        for(int i=0; i<n; i++){
            cout << *(tempArr+i) << " ";
        }
        free(tempArr);
    }else{
        cout << "error: failed to allocate memory!" << endl;
    }
}

int main(){
    int arr[9] = {3, 56, 32, 11, 14, 20, 39, 45, 109};
    MergeSort(arr, 9);

    return 0;
}