1. One-Liner
Quick Sort chooses a pivot, partitions the array into elements ≤ pivot and > pivot, then recursively sorts each side.
2. The Problem It Solves
Fast in-place sorting for general data with excellent average performance; widely used in libraries (often combined with Introsort / Dual-Pivot variants).
3. The Core Idea
Pick a referee (pivot); everyone shorter goes left, taller goes right — the referee stands in their final sorted position; repeat on each side.
4. How It Works (Step-by-Step)
| Step | What Happens |
|---|---|
| 1. | Choose pivot (last element, median-of-three, random) |
| 2. | Partition: reorder range so pivot ends at index p |
| 3. | Recursively sort [lo, p-1] and [p+1, hi] |
| 4. | Base: lo >= hi |
5. Dry Run Example
[3, 8, 1, 5] with pivot 5: after partition something like [3, 1, 5, 8] — 5 is in place; sort [3,1] → [1,3].
6. Key Properties
| Property | Value |
|---|---|
| In-place | Typical Lomuto/Hoare use O(log n) stack |
| Stable | No |
| Random pivot | Reduces worst-case on structured input |
7. Where It Is Used
| Company / System | How They Use It |
|---|---|
C++ std::sort | Introsort (Quick + Heap fallback) |
| Java primitives | Dual-pivot QuickSort |
8. Interview Tips
Master partition invariants; mention median-of-three, random pivot, Introsort; worst-case vs Merge.
9. Comparison with Other Algorithms
| Algorithm | Avg time | Worst | Stable |
|---|---|---|---|
| Quick | O(n log n) | O(n²) | No |
| Merge | O(n log n) | O(n log n) | Yes |
| Heap | O(n log n) | O(n log n) | No |
10. Complexity
| Metric | Value |
|---|---|
| Time (Best) | O(n log n) |
| Time (Average) | O(n log n) |
| Time (Worst) | O(n²) naive pivot |
| Space | O(log n) stack typical |
| Stable? | No |
Implementation Example (PYTHON)
def quick_sort(arr):
def partition(lo, hi):
p = arr[hi]
i = lo
for j in range(lo, hi):
if arr[j] <= p:
arr[i], arr[j] = arr[j], arr[i]
i += 1
arr[i], arr[hi] = arr[hi], arr[i]
return i
def qs(lo, hi):
if lo >= hi:
return
pi = partition(lo, hi)
qs(lo, pi - 1); qs(pi + 1, hi)
qs(0, len(arr) - 1)
return arr