Quick Sort
Software Engineer path · lesson 12 of 99A highly efficient Divide and Conquer algorithm. It picks an element as pivot and partitions the given array around the picked pivot.
Up to 12 whole numbers between -99 and 99, separated by commas or spaces.
On the Already sorted preset, Last makes every split lopsided (n² comparisons); Median of 3 fixes it.
Start: pick a pivot, move smaller values left of it, then sort each side.
- 1quickSort(a, lo, hi):
- 2 if lo >= hi: return
- 3 p = choosePivot(lo, hi); swap(a[p], a[hi])
- 4 i = lo
- 5 for j in lo .. hi-1:
- 6 if a[j] < pivot: swap(a[i], a[j]); i += 1
- 7 swap(a[i], a[hi]) # pivot lands at i
- 8 quickSort(a, lo, i-1); quickSort(a, i+1, hi)
- Comparisons
- 0 / 11
- Swaps
- 0 / 5
Tap any element in the diagram to inspect its state at this step.
Keys: ← → step, Space play/pause. Predict mode pauses before key steps and asks what happens next.
Partition around a pivot
Order one level of quick sort (Lomuto partition).
Tap a piece, then tap where it goes — or drag it. Tap the tray to take one back.
- 1Drop a step here
- 2Drop a step here
- 3Drop a step here
- 4Drop a step here
- 5Drop a step here
Test your knowledge
What is the "Partition" step in Quick Sort?
The short version
Imagine a teacher lining students up by height. She picks one student (the pivot) and says: 'Shorter to the left, taller to the right.' Now she has two smaller groups and repeats. Much faster than moving one student at a time!
In more depth
Partitioning is Key
Quick Sort revolves around the idea of Partitioning. By picking a "pivot" element and organizing the array so that everything smaller is on the left and everything larger is on the right, we effectively place the pivot in its final, correct position.
Why is it so fast?
While its worst-case time complexity is O(n²), its average case is O(n log n) with very small constant factors. It sorts in-place (using little extra memory) and is cache-friendly, often outperforming Merge Sort and Heap Sort in practice on arrays.
Watch out for:
The choice of pivot matters! Picking the first or last element in a sorted array leads to the dreaded O(n²) worst case. Randomized pivots or "Median of Three" helps avoid this.
When to reach for this
- General purpose sorting (standard library implementations often use it)
- When **Space Complexity** matters (O(log n) stack space vs O(n) for Merge Sort)
- When you don't need a Stable Sort
Interview Questions
References & Further Reading
Love this visualization?
Sign up to track your progress, earn achievements, use the AI assistant, and access your personal learning dashboard.
100% free • No credit card required