Quick sort

quickSort.cc

#include <vector>

using namespace std;

void quick_sort(vector<int>& arr, int l, int r);
int quick_partition(vector<int>& arr, int l, int r);

int quick_partition(vector<int>& arr, int l, int r) {
  int pivot = (l + r) >> 1;
  swap(arr[pivot], arr[r]);
  int index = l;
  for (int i = l; i <= r - 1; i++) {
    if (arr[i] <= arr[pivot]) {
      swap(arr[i], arr[index++]);
    }
  }
  swap(arr[r], arr[index]);
  return index;
}

void quick_sort(vector<int>& arr, int l, int r) {
  if (l >= r) return;
  int m = quick_partition(arr, l, r);
  quick_sort(arr, l, m - 1);
  quick_sort(arr, m + 1, r); 
}