#include <bits/stdc++.h>
using namespace std;
using namespace std::chrono;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
const int N = 5e5+86, M = 1, P = 1e9+7, INF = 1e9;
int T,k,n,m,tmp[N];
string s;
bool st[N];

void merge_sort(int a[],int l,int r)
{
    if(l>=r)return;
    int mid=(r+l)/2;//确定分界点
    merge_sort(a,l,mid), merge_sort(a,mid+1,r);//递归分解排序左右两段

    int k=0,i=l,j=mid+1;
    while(i<=mid&&j<=r)//读写头移动比较两段，较小者读入临时数组
    {
        if(a[i]<=a[j])tmp[k++]=a[i++];
        else tmp[k++]=a[j++];
    }

    while(i<=mid)tmp[k++]=a[i++];//剩下的按顺序全部移入临时数组
    while(j<=r)tmp[k++]=a[j++];

    for(i=l,j=0;i<=r;i++,j++)a[i]=tmp[j];//临时数组返回
}

void pop_sort(int q[], int l, int r)
{
    for (int i = l; i <= r-1; i ++ )//遍历直至数组有序
        for (int j = r; j >= i+1; j -- )
            if(q[j] < q[j-1])//未排序区间最大值后置
                swap(q[j],q[j-1]);
}

void select_sort(int q[], int l, int r)
{
    for (int i = l; i <= r-2; i ++ )
    {
        int minx = i;
        for (int j = i+1; j <= r-1; j ++ )
            if(q[minx] > q[j])//寻找未排序区间最小值
                minx = j;
        swap(q[minx],q[i]);//最小值置前
    }//遍历直至数组有序
}

void quick_sort(int a[],int l,int r)
{
    if(l>=r)return;
    int x=a[(l+r)/2],i=l-1,j=r+1;//取区分基准
    while(i<j)//比x大的置于x后，比x小的置于x前
    {
        do i++;while(a[i]<x);//从前往后选取左边第一个比x大的，右边第一个比x小的交换
        do j--;while(a[j]>x);
        if(i<j)swap(a[i],a[j]);
    }
    quick_sort(a,l,j);//递归直至排序区间只剩一个元素返回
    quick_sort(a,j+1,r);
}

void solve()
{    
    int a[N],tmp[N];
    srand(time(nullptr));
    for (int i = 1; i <= 5e4; i ++ )
    {
        a[i] = rand();
    }
    for (int i = 1e4; i <= 5e4; i += 1e4 )
    {
        for (int j = 0; j < i; j ++ )
        {
            tmp[i] = a[i];
        }//数据范围选取

        auto sttime = system_clock::now();
        merge_sort(tmp,0,i);
        auto edtime = system_clock::now();
        duration<double> diff = edtime - sttime;
        cout<<diff.count() * 1000<<" ms"<<endl;
    }
}


int main()
{
    //init();
    T = 1;
    //cin>>T;
    while(T--)
    {
        solve();
    }
    return 0;
}