Quick Sort
Picks a pivot, partitions into smaller and larger, then sorts both sides recursively.
- Comparisons 0
- Swaps 0
- Pivots placed 0
- sorted indices 0
- active range
- pivot
- compare
- swap
- sorted
Pseudocode
1 quickSort(lo, hi)
2 if lo >= hi: return
3 pivot = a[hi]
4 i = lo - 1
5 for j from lo to hi - 1
6 if a[j] <= pivot
7 i = i + 1
8 swap a[i], a[j]
9 swap a[i + 1], a[hi]
10 p = i + 1
11 quickSort(lo, p - 1)
12 quickSort(p + 1, hi)
Step log
How it works, runtime and memory
Quick Sort picks a pivot element (the Lomuto variant used here uses the last element of the range) and partitions the array so that every value left of the pivot is less or equal to the pivot and every value to the right is larger. A pointer i tracks the boundary of the "small" region; a second pointer j walks across all elements, and whenever a[j] <= pivot, a[j] is swapped forward into the small region. At the end the pivot is moved between the two parts. The pivot is now in its final position; the two parts are sorted recursively. With a good pivot choice the range halves every step, producing O(n log n) average and best-case runtime. In the worst case (e.g. an already-sorted input with a bad pivot) the recursion degenerates into a list and the runtime falls to O(n^2). Quick Sort works in-place but needs O(log n) stack memory for the recursion. The algorithm is not stable because swaps over a distance can move equal values past each other.
Complexity
- Best case
O(n log n) - Average case
O(n log n) - Worst case
O(n^2) - Extra space
O(log n)
When to use it
Default sorter in most standard libraries, often as an Introsort variant that falls back to Heap Sort. In practice faster than Merge Sort thanks to in-place operation and cache-friendly memory access. Choose it when memory is tight and stability is not required.