#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

ifstream in_file("algsort.in");

ofstream out_file("algsort.out");


// Function to merge two sorted subarrays into one sorted array
void merge(std::vector<int>& arr, int left, int middle, int right) {
    int leftSize = middle - left + 1;
    int rightSize = right - middle;

    // Create temporary arrays
    std::vector<int> leftArray(leftSize);
    std::vector<int> rightArray(rightSize);

    // Copy data to temporary arrays
    for (int i = 0; i < leftSize; ++i)
        leftArray[i] = arr[left + i];
    for (int j = 0; j < rightSize; ++j)
        rightArray[j] = arr[middle + 1 + j];

    // Merge the temporary arrays back into arr
    int i = 0;  // Initial index of first subarray
    int j = 0;  // Initial index of second subarray
    int k = left;  // Initial index of merged subarray

    while (i < leftSize && j < rightSize) {
        if (leftArray[i] <= rightArray[j]) {
            arr[k] = leftArray[i];
            ++i;
        } else {
            arr[k] = rightArray[j];
            ++j;
        }
        ++k;
    }

    // Copy the remaining elements of leftArray[]
    while (i < leftSize) {
        arr[k] = leftArray[i];
        ++i;
        ++k;
    }

    // Copy the remaining elements of rightArray[]
    while (j < rightSize) {
        arr[k] = rightArray[j];
        ++j;
        ++k;
    }
}

// Recursive function to sort the array using merge sort algorithm
void mergeSort(std::vector<int>& arr, int left, int right) {
    if (left < right) {
        int middle = left + (right - left) / 2;

        // Sort first and second halves
        mergeSort(arr, left, middle);
        mergeSort(arr, middle + 1, right);

        // Merge the sorted halves
        merge(arr, left, middle, right);
    }
}


void mergeSort_1() {
    if (!in_file) {
        return;
    }

    int n;
    in_file >> n;

    vector<int> arr(n);
    for (int i = 0; i < n; ++i)
        in_file >> arr[i];

    mergeSort(arr, 0, n - 1);

    if (!out_file) {
        return;
    }

    for (int i = 0; i < n; ++i)
        out_file << arr[i] << " ";

    out_file.close();
}

int main() {

    mergeSort_1();

    return 0;
}