Quick Sort — Algorithm Visualized
Learn quick sort — Lomuto partition, pivot placement, O(n log n) average, in-place sorting with interactive partition visualizer.
Introduction
Quick sort picks a pivot, partitions the array so elements ≤ pivot are left and greater are right, then recursively sorts both sides. Average O(n log n), in-place, cache-friendly — the workhorse of many standard libraries.
Quick index
| # | Section |
|---|---|
| 1 | How it works |
| 2 | Interactive visualizer |
| 3 | Full implementation |
| 4 | Complexity analysis |
| 5 | Real-life examples |
1. How it works
Pick pivot → partition → pivot in final spot
Recurse on left [lo..p-1] and right [p+1..hi]| Variant | Pivot choice |
|---|---|
| Lomuto | Last element (this visualizer) |
| Hoare | Two pointers from both ends |
| Random | Reduces worst-case on sorted input |
2. Interactive visualizer
Quick Sort — Step Visualizer
Partition around a pivot — elements ≤ pivot left, greater right — then recurse.
Unsorted
n = 7 elements
Pick pivot (Lomuto)
pivot = arr[hi] partition: ≤ pivot left, > pivot right recurse on both sides
In-place partition around last element as pivot.
Time
O(n log n)*
Space
O(log n)
Stable
No
3. Full implementation
function quickSort(arr, lo = 0, hi = arr.length - 1) {
if (lo >= hi) return arr
const p = partition(arr, lo, hi)
quickSort(arr, lo, p - 1)
quickSort(arr, p + 1, hi)
return arr
}
function partition(arr, lo, hi) {
const pivot = arr[hi]
let i = lo - 1
for (let j = lo; j < hi; j++) {
if (arr[j] <= pivot) {
i++
;[arr[i], arr[j]] = [arr[j], arr[i]]
}
}
;[arr[i + 1], arr[hi]] = [arr[hi], arr[i + 1]]
return i + 1
}Function calls with output
// ── Demo calls — output shown on the right ──
const arr = [5, 3, 8, 1, 9, 2, 7]
quickSort(arr) // → [1, 2, 3, 5, 7, 8, 9]
quickSort([1, 2, 3, 4, 5]) // → [1, 2, 3, 4, 5] (worst case with bad pivot)4. Complexity analysis
| Case | Time |
|---|---|
| Average | O(n log n) |
| Worst | O(n²) — bad pivot every time |
| Space | O(log n) stack depth |
| Stable | No |
5. Real-life examples
| Scenario | Why quick sort |
|---|---|
JavaScript Array.sort() | V8 uses Timsort (hybrid), but C++ std::sort is often quicksort intro |
| Database query execution | Sorting result sets in memory — cache-friendly in-place partition |
| Median / percentile dashboards | Quickselect (quick sort variant) finds kth element in O(n) avg |
| File system directory listing | Sort files by name/size in memory before rendering |
| Competitive programming defaults | Fast average case, in-place — default choice for general arrays |
Transaction report sort
Sort 10k transactions by amount — quicksort partitions in-place around a pivot.
Index → value
Daily transaction amounts — unsorted.
Real-world implementation
function quickSort(arr, lo = 0, hi = arr.length - 1) {
if (lo >= hi) return arr
const pivot = arr[hi]
let i = lo
for (let j = lo; j < hi; j++) {
if (arr[j] <= pivot) [arr[i], arr[j]] = [arr[j], arr[i++]]
}
[arr[i], arr[hi]] = [arr[hi], arr[i]]
quickSort(arr, lo, i - 1)
quickSort(arr, i + 1, hi)
return arr
}Full working code for the scenario above.
Function calls with output
// ── Function calls with output ── const txns = [450, 120, 890, 75, 320, 560]
Side output shows return value after each call — step through to trace execution.
Summary
Quick sort partitions in-place around a pivot — fast in practice when pivots are chosen well.
Next reads: Merge Sort · Counting Sort
Subscribe to my newsletter
Stay up to date and get notified when I share new contents.
No spam ever, unsubscribe anytime