Quick sort

O(n log n)

Quick sort chooses a pivot and partitions the array so that smaller values end up left of it and larger ones right — putting the pivot in its final position. It then recurses on each side. On average it is O(n log n) and very cache-friendly, which makes it the default sort in many languages; a bad pivot can degrade it to O(n²).

Array
Edit the input and press Play

How it works

  1. Choose a pivot (here, the last element of the range).
  2. Walk the range, swapping any value smaller than the pivot to the left side.
  3. Swap the pivot into the boundary — it is now in its final place.
  4. Recurse on the sub-ranges left and right of the pivot.

Pseudocode

1quickSort(a, lo, hi):               # O(n log n) avg2  if lo ≥ hi: return3  pivot ← a[hi]4  i ← lo5  for j from lo to hi-1:6    if a[j] < pivot:                 # smaller ones to the left7      swap(a[i], a[j]); i ← i + 18  swap(a[i], a[hi])                  # pivot lands in place9  quickSort(a, lo, i-1); quickSort(a, i+1, hi)