Quick-Sort a Batch With Repeats
MediumSorting & Searching
Problem
A sensor gateway buffers a batch of integer readings readings and must sort them in place before upload. Memory is tight, so you are asked to implement quick sort rather than merge sort.
Batches are often dominated by a few repeated values (a sensor stuck on the same reading). Your sort must stay fast in that case: a batch where every reading is equal must not take quadratic time. Return the sorted readings in non-decreasing order.
Example 1
- Input:
- readings = [4, 1, 4, 9, 4, 0]
- Output:
- [0, 1, 4, 4, 4, 9]
Pivot 4 splits the batch into [1, 0] (smaller), [4, 4, 4] (equal, already final) and [9] (larger).
Example 2
- Input:
- readings = [2, 2, 2]
- Output:
- [2, 2, 2]
Constraints
- 0 ≤ readings.length ≤ 10^5
- -10^9 ≤ readings[i] ≤ 10^9
- Do not call the language's built-in sort.
Hint
Show the first hint
Classic quick sort splits around a pivot into 'smaller' and 'larger or equal'. What happens when every value equals the pivot?
Walkthrough
How to approach it
01Clarify before coding
- Must it be quick sort specifically? Yes: in place, no extra buffer the size of the input.
- How common are duplicates? Very; a batch may be one value repeated 10^5 times.
- Is recursion allowed? Prefer an explicit stack: Python's recursion limit is low and the input can be large.
02Brute force
Two-way quick sort (Lomuto): elements < pivot to the left, the rest to the right, recurse on both.
Cost: O(n log n) on random data but O(n²) when all values are equal: every partition peels off a single element, about 5·10^9 steps for n = 10^5.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.