#include <iostream>
using namespace std;

void quickSort(int l, int r,int *a)
{
    int x = a[l + (r - l) / 2];

    int i = l;
    int j = r;

    while(i <= j)
    {
        while(a[i] < x) i++;
        while(a[j] > x) j--;
        if(i <= j)
        {
            swap(a[i], a[j]);
            i++;
            j--;
        }
    }
    if (i<r)
        quickSort(i, r,a);

    if (l<j)
        quickSort(l, j,a);
}
void bubbleSort(int* a, int n)
{
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < n; ++j)
            if (a[j + 1] < a[j])
                swap(a[j+1],a[j]);
}
void mergeSort(int l,int r,int *a)
{
    if(r==l)
        return;
    if(r-l == 1)
        if(a[r]>a[l])
            return;

    int m = l + (r - l) / 2;
    mergeSort(l,m,a);
    mergeSort(m+1,r,a);

    int buf[r+1];
    int xl=l;
    int xr=m+1;
    int cur = 0;
    while(r-l+1 != cur)
    {
        if(xl >m)
            buf[cur++]=a[xr++];
        else if(xr>r)
            buf[cur++]=a[xl++];
        else if(a[xl]>a[xr])
            buf[cur++]=a[xr++];
        else
            buf[cur++]=a[xl++];
    }
    for(int i = 0;i<cur;i++)
        a[i+l]=buf[i];

}
void init(int *a,int n)
{
    for(int i = 0; i < n; i++)
    {
        a[i] = rand()%100;
    }
}
void show(int *a,int n)
{
    for(int i = 0; i < n; i++)
    {
        cout<<a[i]<<" ";
    }
}
int main()
{
    srand(time(NULL));
    long int time[2];
    int n;
    cin >> n;
    int a[n];

    cout << "INITED" << endl;
    init(a,n);
   // show(a,n);

    cout << endl << "MergeSort ";
    time[0] = clock();
    mergeSort(0, n-1,a);
    time[1] = clock() - time[0];
    cout << "TIME: "<< ((float)time[1])/CLOCKS_PER_SEC <<endl;
   // show(a,n);

    cout << endl << "QuickSort ";
    time[0] = clock();
    quickSort(0, n-1,a);
    time[1] = clock() - time[0];
    cout << "TIME: "<< ((float)time[1])/CLOCKS_PER_SEC <<endl;
   // show(a,n);

    cout << endl << "BubbleSort ";
    time[0] = clock();
    bubbleSort(a,n-1);
    time[1] = clock()-time[1];
    cout << "TIME: "<< ((float)time[1])/CLOCKS_PER_SEC <<endl;
  //  show(a,n);

    return 0;
}