Algorithms/Sorting/Quick Sort

Quick Sort

Divide-and-conquer sort that partitions the array around a pivot. Average O(n log n) with great cache locality — the default sort in many standard libraries.

SortingDivide & ConquerIn-PlaceO(n log n) avg

Comparisonsso far

Writesso far

Partition Diagram

Main array with pivot highlighted and the i / j boundary

default comparing swapping sorted

Main arrayin-place

Arrayn = 24

109

1110

1211

1312

1413

1514

1615

1716

1817

1918

2019

2120

2221

2322

2423

✓

RecursionAll sorted — no active range.

1 / 0

Speed

Preset

n24

Pivot

quick-sort.js

1function quickSort(arr, lo, hi) {

2 if (lo >= hi) return; // base case

4 // PARTITION: pick a pivot, then split the range

5 const pivotIdx = pickPivot(arr, lo, hi);

6 swap(arr, pivotIdx, hi); // move pivot to the end

7 const p = lomutoPart(arr, lo, hi); // returns pivot's final index

9 // RECURSE on either side of the pivot

10 quickSort(arr, lo, p - 1);

11 quickSort(arr, p + 1, hi);

12}

14function lomutoPart(arr, lo, hi) {

15 const pivot = arr[hi]; // pivot is at arr[hi]

16 let i = lo - 1; // boundary of '<= pivot' region

18 for (let j = lo; j < hi; j++) {

19 if (arr[j] <= pivot) {

20 i++; // grow '<= pivot' region

21 swap(arr, i, j); // move element into the region

22 }

23 }

24 swap(arr, i + 1, hi); // pivot into its final spot

25 return i + 1; // final pivot index

26}

28// Pivot strategies

29pickPivot: 'last' | 'random' | 'median-of-three'

Algorithm Explanation

Quick sort is a divide-and-conquer algorithm that works by selecting a pivot element from the array and partitioning the other elements into two sub-arrays — those less than the pivot and those greater than it. It then recursively sorts the sub-arrays. Invented by Tony Hoare in 1959, it's the default sort in many standard libraries (glibc, V8, Java for primitives) thanks to its excellent cache behaviour and small constant factors.

⚙️ How It Works

Pick a pivot from the range. Common strategies: the last element, a random element, or the median of three (lo, mid, hi).
Partition the range so that every element to the pivot's left is ≤ pivot and every element to its right is > pivot. After this step the pivot is in its final sorted position.
Recurse on the left sub-range [lo..p-1] and the right sub-range [p+1..hi].
Base case — a range of length 0 or 1 is already sorted; the recursion bottoms out.

🧩 The Lomuto Partition

We use the Lomuto partition scheme because it's the easiest to visualize. It maintains a single boundary pointer i that separates the "≤ pivot" region (left) from the "untested" region (right). A second pointer j walks left to right through the range, and i only advances when arr[j] ≤ pivot — at which point the element at i is swapped with the element at j.

💡 In-place & cache-friendly: Quick sort works directly on the input array using only O(log n) stack space (for the recursion), with very few writes and excellent sequential memory access. This is why it tends to beat merge sort in practice despite the same average-case complexity.

⚖️ Quick vs Merge vs Heap

Merge sort

Guaranteed O(n log n).
Stable — preserves order of equals.
Needs O(n) extra buffer.
Great for linked lists & external sort.

Quick sort (this page)

O(n log n) average, O(n²) worst case.
Not stable by default.
In-place (O(log n) stack).
Faster in practice on random data due to cache locality.

Heap sort

Guaranteed O(n log n).
Not stable.
In-place (O(1) extra).
Worse cache behaviour than quick / merge sort.

Lomuto partition with a single boundary pointer i — try the three pivot strategies on reversed input to see why the choice matters.