#include <iostream>
#include <cstring>
#include <stdlib.h>
using namespace std;

void merge(int *R, int low, int mid, int high){  //将相邻的数组合并
    int *r;
    r = (int *)malloc((high - low + 1)*sizeof(int));
    int i = low, j = mid + 1, p = 0;
    while(i <= mid && j <= high){
        r[p++] = ((R[i] > R[j]) ? R[j++] : R[i++]);
    }
    while(i <= mid){
        r[p++] = R[i++];
    }
    while(j <= high){
        r[p++] = R[j++];
    }
    for(i = low, j = 0; j < p; j++, i++)
        R[i] = r[j];
}

void MergeSort(int *R, int low, int high){
    int mid;
    if(low < high){   // 注意递归退出条件 （while or if）
        mid = (low + high) / 2;
        MergeSort(R, low, mid);
        MergeSort(R, mid + 1, high);
        merge(R, low, mid, high);
    }
}

int main(){
    int R[1000];
    int low = 1, high = 0;
    cin >> high;
    cout << "排序前的数组："  << endl;
    for(int i = 1; i <= high; i++){
        cin >> R[i];
    }
    MergeSort(R, low, high);
    cout << "排序后：" << endl;
    for(int i = 1; i <= high; i++)
        cout << R[i] << " ";
    return 0;
}

6-归并排序