Quicksort

Quicksort, developed by Tony Hoare in 1959, has a worst-case run time of $O(n$²), but is still often the best choice of sorting algorithm because it's remarkably efficient on average. It's expected run time is $O(n\; log\; n)$, the constants hidden in big-$O$ notation are small, and it sorts in-place (unlike merge sort).

Similarly to merge sort, quicksort's approach could be characterized as a divide-and-conquer one:

1. Partition the array into two (possibly empty) subarrays like this:
   1. Pick a pivot index
   2. Iterate over the array, swapping array elements that are smaller than the pivot into the low section, using a variable to track the size of the low section
   3. After iterating over the whole array, put the pivot in between the low sub array and the high subarray
2. Recursively sort the two subarrays

int partition(int *A, int p, int r) {
  int x = A[r], i = p - 1;
  for (int j=p; j<r; j++)
    if (A[j] <= x)
      swap(&A[++i], &A[j]);
  swap(&A[i+1], &A[r]);
  return i+1;
}

void quicksort(int *A, int p, int r) {
  if (p < r) {
    int q = partition(A, p, r);
    quicksort(A, p, q-1);
    quicksort(A, q+1, r);
  }
}