#include <iostream>
#include <string>
using namespace std;


void merge(int a[],int c[],int first,int mid,int last){
    int i = first;
    int j = mid+1;
    int k = first;
    while(i<=mid && j<=last){
        if(a[i] <= a[j]){
            c[k] = a[i];
            k++;
            i++;
        }
        else{
            c[k] = a[j];
            k++;
            j++;
        }
    }
    while(i<=mid){
        c[k]=a[i];
        k++;
        i++;
    }
    while(j<=last){
        c[k]=a[j];
        k++;
        j++;
    }
for(int i=first;i<=last;i++)a[i]=c[i];
}

void mergeSort(int a[],int c[],int first , int last){
    if(first<last){
    int mid = (first+last)/2;
    mergeSort(a,c,first,mid);
    mergeSort(a,c,mid+1,last);
    merge(a,c,first,mid,last);
}
}

int  main(){
    int a[99] = {5,4,3,2,1};
    int c[99];
    mergeSort(a,c,0,4);
    for(int i = 0 ;i<5;i++){
        cout<<a[i]<<" ";
    }
}

归并排序的思想是分而治之，将数组不断分割，最后将两部分数组合并，通过判断第一部分和第二部分数组当前元素的大小来合并，不断合并直到完成排序。

归并排序是稳定的排序方式，归并排序的比较次数小于快速排序的比较次数，移动次数一般多于快速排序的移动次数，归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n)。