#include <algorithm>
#include <vector>
using namespace std;

void merge(vector<int>& list, int left, int mid, int right)
{
    int i = left, j = mid + 1;
    int m = mid, n = right;
    int k = 0;
    vector<int> temp(right - left + 1, 0);
    while (i <= m&&j <= n)
    {
        if (list[i] <= list[j])
            temp[k++] = list[i++];
        else
            temp[k++] = list[j++];
    }
    while (i <= m)
        temp[k++] = list[i++];
    while (j < n)
        temp[k++] = list[j++];
    for (i = 0; i < k; ++i)
        list[left + i] = temp[i];
}

void mergesort(vector<int>& list, int left, int right)
{
    if (left >= right)
        return;
    int mid = (left + right) / 2;
    mergesort(list, left, mid);
    mergesort(list, mid + 1, right);
    merge(list, left, mid, right);
}

void MergeSort(vector<int>& list)
{
    mergesort(list, 0, list.size() - 1);
}