#include <bits/stdc++.h>

using namespace std;

// Merge two sorted sub‑vectors [left, mid] and (mid, right]
void merge(vector<int> &array, int left, int right, int mid) {
    // Lengths of the two sub‑arrays
    int left_len = mid - left + 1;
    int right_len = right - mid;

    // copy the halves into temporary vectors
    vector<int> left_vec(array.begin() + left,
                              array.begin() + left + left_len);
    vector<int> right_vec(array.begin() + mid + 1,
                               array.begin() + mid + 1 + right_len);

    int left_i = 0;
    int right_i = 0;
    int merged_i = left;

    // Main merge loop
    while (left_i < left_len && right_i < right_len) {
        if (left_vec[left_i] <= right_vec[right_i]) {
            array[merged_i++] = left_vec[left_i++];
        } else {
            array[merged_i++] = right_vec[right_i++];
        }
    }

    // Copy any remaining elements from the left half
    while (left_i < left_len) {
        array[merged_i++] = left_vec[left_i++];
    }

    // Copy any remaining elements from the right half
    while (right_i < right_len) {
        array[merged_i++] = right_vec[right_i++];
    }
}

// merge_sort(array, left, right)
void merge_sort(vector<int> &array, int left, int right) {
    if (left >= right) return; // Base case
    int mid = left + (right - left) / 2; // Floor division
    merge_sort(array, left, mid);
    merge_sort(array, mid + 1, right);
    merge(array, left, right, mid);
}

// Convenience wrapper for the whole array
void merge_sort(vector<int> &array) {
    if (array.empty())
        return;
    merge_sort(array, 0, array.size() - 1);
}