Quick Sort & Top Picks
Tunebox's home screen shows Top picks: the 10 most-played tracks from a library of 50,000. Sorting all 50,000 to keep 10 is wasted work. Quick sort's core move — partitioning around a pivot — sorts in place in O(n log n) on average, and the same move finds the top 10 in about O(n) without sorting the rest.
Partitioning around a pivot
Pick one value, the pivot. Rearrange the list so everything smaller than the pivot sits to its left and everything else to its right. The pivot is then in its final sorted position — and no value on one side ever needs comparing with a value on the other again.
The Lomuto scheme uses the last value as the pivot and one boundary index
i: everything before i is known to be smaller than the pivot. Scan the rest
with j; each smaller value is swapped to i, growing that region by one. At the
end, swap the pivot into slot i — right after the smaller values.
Partitioning puts the pivot in place. It does not sort either side:
def partition(items, lo, hi):
pivot = items[hi]
i = lo
for j in range(lo, hi):
if items[j] < pivot:
items[i], items[j] = items[j], items[i]
i += 1
items[i], items[hi] = items[hi], items[i]
return i
nums = [9, 3, 7, 1, 5]
partition(nums, 0, len(nums) - 1)
print(nums)Quick sort: partition, then recurse on both sides
Once the pivot is placed, sort the left side and the right side the same way. Everything happens inside the one list — no new lists are built.
This version forgets the last line of partition:
This should print the plays sorted low→high. It prints [42, 7, 19, 3, 88, 56] — the recursion trusts an index the pivot never moved to.
Pivot choice and the worst case
On average the pivot lands near the middle, the list halves each level, and quick sort does O(n log n) work. But nothing forces a good split. Take the last value as pivot on a list that's already sorted: the pivot is the maximum, the right side is empty, and the left side is only one smaller.
count = 0
def quick_sort(items, lo, hi):
global count
if lo >= hi:
return
pivot, i = items[hi], lo
for j in range(lo, hi):
count += 1
if items[j] < pivot:
items[i], items[j] = items[j], items[i]
i += 1
items[i], items[hi] = items[hi], items[i]
quick_sort(items, lo, i - 1)
quick_sort(items, i + 1, hi)
quick_sort([1, 2, 3, 4, 5, 6, 7, 8], 0, 7)
print(count)The worst case appears when pivots are consistently the smallest or largest: sorted or reverse-sorted input with a first/last pivot, or many equal values. The fixes:
- pick the middle value (swap it to
hifirst) — sorted input becomes the best case; - pick randomly — no fixed input is reliably bad;
- three-way partition (below) — for lots of duplicates.
❓ Cross-question — "With an O(n²) worst case, why is quick sort so popular?" It sorts in place, its inner loop is a tight scan that's kind to the CPU cache, and with a sensible pivot the worst case essentially never happens. Production versions also switch to insertion sort for tiny ranges and guard against bad inputs.
In place, and not stable
Quick sort needs no second list — only the recursion stack: O(log n) deep on
average, O(n) in the worst case. That's its edge over merge sort's O(n) buffer.
The price is stability: a partition swap can throw an item far past an equal
one, so ties don't keep their order. When ties matter, give every item a unique,
total order — like (-plays, title) — and stability stops mattering.
Quickselect: the k-th item without sorting
After one partition, the pivot sits at its final index p. If you want the item
that belongs at index k, you now know which side it's on — so recurse into
only that side and ignore the other.
Each step throws away one side. With decent pivots that's n + n/2 + n/4 + … ≈ 2n comparisons: O(n) on average. And when it stops, everything left of index k is ≤ the k-th value — so the k smallest are sitting at the front, unsorted. Sort just those k, and you have Top picks.
| operation | average | worst | extra space | stable |
|---|---|---|---|---|
| partition (Lomuto) | O(n) | O(n) | O(1) | no |
| quick sort | O(n log n) | O(n²) | O(log n) stack avg, O(n) worst | no |
| quickselect (k-th item) | O(n) | O(n²) | O(1) iterative | — |
| top k: quickselect + sort k | O(n + k log k) | O(n²) | O(n) copy | — |
top k: sorted(...)[:k] |
O(n log n) | O(n log n) | O(n) | yes |
top k: heapq.nsmallest(k, key=…) |
O(n log k) | O(n log k) | O(k) | — |
Idioms & real-world patterns
A tuple key makes the order total — and works in production
"Most plays first, ties A→Z" is one comparison if each track becomes the tuple
(-plays, title): tuples compare element by element, and negating plays turns
high→low into low→high. The same key drives the standard library's top-k:
For a few thousand tracks either is plenty fast. Quickselect earns its keep when n is huge.
Coming from Java/JS: Java's
Arrays.sort(int[])is a dual-pivot quick sort. C++ has quickselect built in asstd::nth_element. Python has neither exposed —sorted()is Timsort, andheapqcovers top-k.
⚡ Advanced — three-way partition for duplicates
Star ratings have only five values, so a normal partition keeps re-scanning equal items. Split into less / equal / greater in one pass instead, and never recurse into the equal middle:
🎯 Your turn
Write top_k_tracks(tracks, k). Each track is {"title": ..., "plays": ...},
titles are unique. Return the titles of the k most-played tracks, ordered by
plays high→low, ties broken by title A→Z. If k is bigger than the
library, return every track in that order; if k <= 0, return []:
top_k_tracks([{"title": "Dawn", "plays": 30}, {"title": "Aria", "plays": 50}, {"title": "Blue", "plays": 30}, {"title": "Cove", "plays": 10}], 2)→["Aria", "Blue"]
Hint — turn each track into (-plays, title) so "smaller tuple" means
"ranks higher", quickselect the k smallest to the front, then sort just those k.
Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green = this piece of Tunebox is built. ✅