#include <stdio.h>
#include <conio.h>

void mergesort(int x[], int t[], int i, int j){
    int x1 = i, x2 = (j + i)/2 + 1, k, y;
    if (i == j){
		return;
	} else { 
        if (i + 1 == j){
            if (x[i] > x[j]) {
				x[i] = x[i] + x[j] - (x[j] = x[i]); // b = b + a - (a=b);
			}
		} else {
            mergesort(x, t, i, (j + i)/2);
            mergesort(x, t, (j + i)/2 + 1, j);
			k = 0;
            while(x1 < (j + i)/2+1 && x2 <= j){
                if (x[x1] < x[x2]){
					t[k++] = x[x1++];
				} else {
					t[k++] = x[x2++];
				}
            }
			if (x1 == (j + i)/2 + 1){
				for(x2; x2 <= j; x2++){
					t[k++] = x[x2];
				}
			}
			if (x2 == j + 1){
				for (x1; x1 < (j + i)/2 + 2; x1++){
					t[k++] = x[x1];
				}
			}
			y = 0;
			for(x1 = i; x1 <= j; x1++){
			   x[x1] = t[y++];
			}
        }
	}
}

void afisare_vector(int v[], int nr){
	int i;
	printf("\n");
	printf("Vectorul sortat este = ");
	for(i = 0; i < nr; i++){
		printf("%d ", v[i]);
	}
}

int main(){
    int v[100], t[100], nr_elemente, i;
    freopen("algsort.in.in", "r", stdin);
    freopen("algsort.out.in", "r", stdin);
    scanf("%d", &nr_elemente);
	for(i = 0; i < nr_elemente; i++){
		scanf("%d", &v[i]);
	}
    mergesort(v, t, 0, nr_elemente-1);
	afisare_vector(v, nr_elemente);
}