#include <stdio.h>

void merge(int a[], int b[], int low, int mid, int high) {
    int h = low, j = mid + 1, i = low;
    
    while (h <= mid && j <= high) {
        if (a[h] <= a[j]) {
            b[i] = a[h];
            h += 1;
        } else {
            b[i] = a[j];
            j += 1;
        }
        i += 1;
    }
    if (h > mid) {
        for (int k = j; k <= high; k++) {
            b[i] = a[k];
            i += 1;
        }
    } else {
        
        for (int k = h; k <= mid; k++) {
            b[i] = a[k];
            i += 1;
        }
    }
    for (int k = low; k <= high; k++) {
        a[k] = b[k];
    }
}

void mergeSort(int a[], int b[], int low, int high) {
    if (low < high) {
        int mid = (low + high) / 2;
        mergeSort(a, b, low, mid); 
        mergeSort(a, b, mid + 1, high); 
        merge(a, b, low, mid, high); 
    }
}

int main() {
    int n;
    printf("Enter Size: ");
    scanf("%d", &n);

    int a[n], b[n];
    printf("Enter Elements: ");
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    mergeSort(a, b, 0, n - 1);

    printf("Sorted Elements: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");

    return 0;
}