#include <iostream>
#include <vector>

using namespace std;

void swap(int &a, int &b)
{
    int temp;
    a = b;
    b = temp;
}

int split_array(vector<int>& array, int pivot, int start_index, int end_index)
{
    int left_boundary = start_index;
    int right_boundary = end_index;

    while (left_boundary < right_boundary) {
        while (pivot < array[right_boundary] && right_boundary > left_boundary) {
            right_boundary--;
        }
        
        swap(array[left_boundary], array[right_boundary]);

        while (pivot >= array[left_boundary] && left_boundary < right_boundary) {
            left_boundary++;
        }
      
        swap(array[right_boundary], array[left_boundary]);
    }

    return left_boundary;
}

void quicksort(vector<int>& array, int start_index, int end_index)
{
    int pivot = array[start_index];
    int split_point;
     
    if (end_index > start_index) {
        split_point = split_array(array, pivot, start_index, end_index);
        array[split_point] = pivot;
        quicksort(array, start_index, split_point-1);
        quicksort(array, split_point+1, end_index);
    }
}