- Explain the pivot, scan pointer, partition boundary, and active range.
- Trace a Lomuto partition until the pivot reaches its final position.
- Implement Quick Sort in JavaScript, Python, Java, or C++.
- Recognize how pivot quality changes recursion depth from O(log n) to O(n).
Partitioning, made visible
Choose a pivot.
Partition the rest.
Quick Sort places one pivot in its final position, then repeats the same idea independently on the ranges to its left and right.
Mini example[ 7, 2, 5 ]
01
725
pivot 502
275
partition03
257
pivot fixedKey idea A completed partition guarantees that every value left of the pivot is no larger and every value right is larger.
Before you start
What you will learn
A clear finish line for the lesson, plus the small amount of knowledge you need before beginning.
- Arrays, indexes, and swaps
- Functions and recursion basics
- Big O and logarithms from the glossary
01Understand02Visualize03Trace04Code05Complexity06Quiz07Challenge08Use cases
01 — The idea
How Quick Sort thinks
Can one chosen value divide the current range into two smaller sorting problems?
725
Choose the pivot
This lesson uses the final value in the active range as the pivot.
2≤ 5 | > 57
Move the boundary
Scan left to right and grow a region containing values no larger than the pivot.
257
Fix and recurse
Place the pivot after that region, then sort the ranges on both sides.
02 — Try it yourself
Watch each pivot divide its range
Follow the active recursive range, scan pointer, smaller-value boundary, and pivots already fixed.
3–10 values, each from 1 to 99
Active range: 0–6Boundary: 0Fixed pivots: 0
Comparisons0
Swaps0
Partitions0
Scanning Pivot Fixed
Dry-run trace
Turn each animation into a written decision
| Step | Pass | Action | Scan / pivot | Current array | Swaps |
|---|---|---|---|---|---|
| 0 | — | Ready | Pivot 6 | [10, 7, 8, 9, 1, 5, 6] | 0 |
The highlighted row always matches the visualization above. Step forward to extend the trace.
03 — Read the code
From partition boundary to working code
Compare the same Lomuto partition and shrinking recursive ranges across all four languages.
01function quickSort(numbers) {02 const array = [...numbers];03 sortRange(array, 0, array.length - 1);04 return array;05}06 07function sortRange(array, start, end) {08 if (start >= end) return;09 const pivotIndex = partition(array, start, end);10 sortRange(array, start, pivotIndex - 1);11 sortRange(array, pivotIndex + 1, end);12}13 14function partition(array, start, end) {15 const pivot = array[end];16 let boundary = start;17 for (let scan = start; scan < end; scan++) {18 if (array[scan] <= pivot) {19 [array[boundary], array[scan]] = [array[scan], array[boundary]];20 boundary++;21 }22 }23 [array[boundary], array[end]] = [array[end], array[boundary]];24 return boundary;25}04 — Avoid the traps
Common mistakes
These bugs often produce an answer that looks almost right. Learn the symptom and the correction together.
Including the pivot in the scan
Symptom: The pivot moves before all other values have been classified.
Correction: Scan only through end − 1, then place the pivot after the loop.
Recursing over the pivot again
Symptom: Ranges fail to shrink and recursion may never finish.
Correction: Recurse on start through pivotIndex − 1 and pivotIndex + 1 through end.
Moving the boundary for large values
Symptom: Values greater than the pivot leak into the left partition.
Correction: Advance the boundary only when the scanned value belongs on the pivot's left side.
Assuming every pivot is balanced
Symptom: Worst-case time is incorrectly reported as O(n log n).
Correction: An extreme pivot can leave one empty side and create O(n) recursion depth.
05 — Check yourself
Check your understanding
Answer 4 questions, then reveal the reasoning. Your progress stays on this device—no account required.
0 of 4 answered
Answer every question to check your work.
06 — Mini game
Build a pivot partition
Classify every scanned value around the final pivot, just as the partition loop does.
Rule Send values ≤ pivot left and values > pivot right. The pivot remains between both groups.
Classify 70 picks
Pivot6Scanning7
6
◆
Is 7 no larger than pivot 6?
07 — Use it wisely
Where Quick Sort fits
In-memory arrays
Good cache behavior and small constants make it fast for many practical array workloads.
Great average caseLow extra memory
In-place partitioning needs no O(n) merge buffer, only recursive stack space.
Good fitHybrid library sorts
Randomized pivots and fallback strategies can control its worst-case behavior.
Common building blockStable or adversarial sorting
This version is unstable, and predictable extreme pivots can cause quadratic time.
Use safeguardsLesson progress
Finish this lesson with confidence
Use this private checklist to confirm what you learned. Progress stays only in this browser.
0 of 4 complete0%
Complete every checklist item to finish the lesson.