#include <iostream>
#include <vector>
 
using namespace std;
 
void merge(vector<int> &arr,int L,int mid,int R)
{
    int *help = new int(R-L+1);
    int p1=L,p2=mid+1,i=0;
    while(p1<=mid && p2<=R)
    {
        help[i++] = arr[p1]>arr[p2] ? arr[p2++] : arr[p1++];
    }
    while(p1<=mid)
        help[i++] = arr[p1++];
    while(p2<=R)
        help[i++] = arr[p2++];
 
    for (int i=0;i<R-L+1;i++)
    {
        arr[L+i] = help[i];
    }
}
void sortprocess(vector<int> &arr,int L,int R)
{
    if (L < R)
    {
        int mid = L + ((R-L)>>2);  //  (L+R)/2
        sortprocess(arr,L,mid);
        sortprocess(arr,mid+1,R);
        merge(arr,L,mid,R);
    }
}
 
void MergeSort(vector<int> &arr,int L,int R)
{
    if (arr.size()<2)   return;
    sortprocess(arr,L,R);
}
 
 
int main()
{
    vector<int> arr;
    int n,temp;
    cin>>n;  //输入n个数
    for (int i=0;i<n;i++)
    {
        cin>>temp;  //输入数据
        arr.push_back(temp);
    }
 
    MergeSort(arr,0,arr.size()-1);
 
    for(int i=0;i<arr.size();i++)   cout<<arr[i]<<endl;
 
    system("pause");
    return 0;
 
}

#include<stdio.h>
#define ArrLen 20
void printList(int arr[], int len) {
    int i;
    for (i = 0; i < len; i++) {
        printf("%d\t", arr[i]);
    }
}
void merge(int arr[], int start, int mid, int end) {
    int result[ArrLen];   // 开一个空的数组
    int k = 0;
    int i = start;
    int j = mid + 1;
    while (i <= mid && j <= end) 
　　{
        if (arr[i] < arr[j])   result[k++] = arr[i++];     
           else    result[k++] = arr[j++];  
    }
if (i == mid + 1) {   // 如果只剩右边
        while(j <= end)
            result[k++] = arr[j++];
    }
    if (j == end + 1) {   // 如果只剩左边
        while (i <= mid)
            result[k++] = arr[i++];
    }
    for (j = 0, i = start ; j < k; i++, j++) {
        arr[i] = result[j];
    }
}
 
void mergeSort(int arr[], int start, int end) {
    if (start >= end)
        return;
    int mid = ( start + end ) / 2;
    mergeSort(arr, start, mid);      // 左边
    mergeSort(arr, mid + 1, end);   // 右边
    merge(arr, start, mid, end);    // 合并
}
 
int main()
{
    int arr[] = {4, 7, 6, 5, 2, 1, 8, 2, 9, 1};
    mergeSort(arr, 0, 9);
    printList(arr, 10);
    system("pause");
    return 0;
}