//
//  main.cpp
//  MergeSort
//
//  Created by Alex Petrache on 06.05.2015.
//  Copyright (c) 2015 Alex Petrache. All rights reserved.
//

#include <iostream>
#include <fstream>
#define N_MAX 500009
using namespace std;

int helper[N_MAX];

void merge(int a[], int helper[], int left, int middle, int right){
    int i;
    for(i=left;i<=right;i++)
        helper[i]=a[i];
    int helperleft=left;
    int helperright=middle+1;
    int current=left;
    
    while(helperleft<=middle && helperright<=right){
        if(helper[helperleft]<=helper[helperright])
            a[current]=helper[helperleft++];
        else
            a[current]=helper[helperright++];
        current++;
    }
    int remaining=middle-helperleft;
    for(i=0;i<=remaining;i++)
        a[current+i]=helper[helperleft+i];
}

void mergesort(int a[], int helper[], int left, int right){
    if(left<right){
        int middle=(left+right)/2;
                cout<<left<<" "<<middle<<" "<<right<<endl;
        mergesort( a,  helper, left, middle);
        mergesort( a,  helper, middle+1, right);
        merge(a,helper,left,middle,right);
    }
}

int main(int argc, const char * argv[]) {
    int n, a[N_MAX],i;
    ifstream f("algsort.in");
    //ifstream f("/Users/alexpetrache/Documents/Programare/Xcode/MergeSort/MergeSort/algsort.in");
    ofstream g("algsort.out");
    
    f>>n;
    for(i=0;i<n;i++)
        f>>a[i];
    
    mergesort(a,helper,0,n-1);
    
    for(i=0;i<n;i++)
        g<<a[i]<<" ";
    return 0;
}