Quick Sort

Pick a pivot, partition elements into 'less than' and 'greater than' groups, then recursively sort each partition. Uses Lomuto partitioning here.

time O(n log n) avg, O(n²) worst

space O(log n)

Input

Press Tab out of the box or click Resetto regenerate frames from the current input.

Visualization

No frames yet — edit input and click Run.

—

Pseudocode

quickSort(a, lo, hi):
  if lo >= hi: return
  p = partition(a, lo, hi)    // pivot = a[hi]
  quickSort(a, lo, p-1)
  quickSort(a, p+1, hi)