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

int partition(vector<int>& list, int left, int right)
{
    int& key = list[left];
    while (left < right)
    {
        while (left < right&&list[right] >= key)
            right--;
        while (left < right&&list[left] <= key)
            left++;
        swap(list[left], list[right]);
    }
    swap(list[left], key);
    return left;
}

void quicksort(vector<int>& list, int left, int right)
{
    if (left >= right)
        return;
    int index = partition(list, left, right);
    quicksort(list, left, index - 1);
    quicksort(list, index + 1, right);
}

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