#include <iostream>
#include <vector>

// IN-PLACE MERGE SORT

void merge(std::vector<int>& arr, size_t left, size_t mid, size_t right) {
    // индекс начала второй "половины" для слияния
    size_t left_2 = mid + 1;

    // половины уже отсортированы
    if (arr[mid] <= arr[left_2]) return;

    while (left <= mid && left_2 <= right) {
        // первые элементы в правильном порядке
        if (arr[left] <= arr[left_2]) left++;
        else {
            // вставляем на правильное место left элемент arr[left_2]
            // запоминаем его и его индекс
            int value = arr[left_2];
            size_t ind = left_2;

            // сдвигаем все элементы между left и left_2 вправо
            // и записываем на место left элемент arr[left_2]
            while (ind != left) {
                arr[ind] = arr[ind - 1];
                ind--;
            }
            arr[left] = value;

            // передвигаем все рабочие индексы
            left++;
            mid++;
            left_2++;
        }
    }
}

// основной метод сортировки
void mergeSort(std::vector<int>& arr, size_t left, size_t right) {
    if (left < right) {
        size_t mid = left + (right - left) / 2;

        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        merge(arr, left, mid, right);
    }
}

int main() {
    std::vector<int> v {-1, -2, 5, 6, 6, 7, 7, 8, -9, -100};

    mergeSort(v, 0, v.size() - 1);

    for (int elem : v) {
        std::cout << elem << " ";
    }
}