Problem overview
The method sort receives an array of numbers, nums, and sorts it in ascending order in place using Quick Sort. It returns nothing. The statement asks for O(n log n) time and O(log n) extra space.
For nums = [3, 1, 3, 2, 5, 4], the array becomes [1, 2, 3, 3, 4, 5].
Approach: partition around a pivot, then recurse
Quick Sort also divides and conquers, but it does its work before the recursion rather than after it:
- Pick one element, the pivot.
- Partition the range: move everything not larger than the pivot to its left and everything larger to its right. The pivot lands in the position it will have in the final sorted array.
- Sort the part left of the pivot and the part right of the pivot the same way. The pivot itself is never touched again.
There is no merge step and no buffer: partitioning rearranges the array in place, which is why the extra space is only the recursion stack. If each pivot splits its range roughly in half, there are about log2(n) levels and each level does O(n) partitioning work, giving O(n log n).
The weak spot is the pivot choice. If the pivot is always the smallest or largest element, one side is empty and the other has everything else, so the recursion is n levels deep and the total work is O(n²). Always picking the last element does exactly that on an already sorted array. This lesson picks a random index, which makes a bad split on every level extremely unlikely whatever order the input comes in. The O(n log n) time is therefore an expected time, not a guarantee.
Step by step
- Sort the whole array from
sortwiththis.quickSort(nums, 0, nums.length - 1). Both bounds are inclusive. - Declare
quickSortwithnums,leftandright, returningvoid. - Base case. If
left >= right, the range holds at most one element and is already sorted. Using>=rather than===also covers ranges that came out empty. - Partition with
this.partition(nums, left, right)and keep the returned index inpivot. - Sort the left part,
lefttopivot - 1. - Sort the right part,
pivot + 1toright. - Declare
partitionwith the same three parameters, returning the pivot's final index as anumber. - Pick a random index in
lefttoright:Math.random()gives a number from 0 up to but not including 1, soleft + Math.floor(Math.random() * (right - left + 1))covers every index equally. - Move that element to the end by swapping it with
nums[right]. Now the pivot sits out of the way. - Save the pivot value as
value. - Track
correctIndex, starting atleft: the slot where the next element not larger thanvaluebelongs. Everything before it is already not larger thanvalue. - Scan with
ifromlefttorightinclusive. - When
nums[i] <= value, swap it withnums[correctIndex]and incrementcorrectIndex. - Return
correctIndex - 1. The scan includes the pivot atright, which is the last element moved into the left part, so it ends up atcorrectIndex - 1.
The solution in TypeScript
class Solution {
partition(nums: number[], left: number, right: number): number {
let randomIndex = left + Math.floor(Math.random() * (right - left + 1));
[nums[randomIndex], nums[right]] = [nums[right], nums[randomIndex]];
let value = nums[right];
let correctIndex = left;
for (let i = left; i <= right; ++i) {
if (nums[i] <= value) {
[nums[i], nums[correctIndex]] = [nums[correctIndex], nums[i]];
correctIndex++;
}
}
return correctIndex - 1;
}
quickSort(nums: number[], left: number, right: number): void {
if (left >= right) {
return;
}
let pivot = this.partition(nums, left, right);
this.quickSort(nums, left, pivot - 1);
this.quickSort(nums, pivot + 1, right);
}
sort(nums: number[]): void {
this.quickSort(nums, 0, nums.length - 1);
}
}
Here is one partition by hand, with the pivot already at the end. For [3, 1, 3, 2, 5, 4] the pivot value is 4. Every element except 5 is not larger than 4 and is swapped into the growing left part, and 5 stays behind it. The last element, the pivot itself, is swapped into the slot just after the small ones. The array becomes [3, 1, 3, 2, 4, 5] and the function returns 4: the 4 is in its final place, and [3, 1, 3, 2] is left to sort.
Some TypeScript details:
- Swapping with destructuring.
[a, b] = [b, a]builds the array on the right first and then assigns its elements, so no temporary variable is needed. It also works on array elements, as in[nums[i], nums[correctIndex]] = [nums[correctIndex], nums[i]]. WheniequalscorrectIndex, the swap does nothing. - The line before a destructuring swap. A statement starting with
[can be read as an index into the previous line if that line has no semicolon. The reference ends every line with a semicolon, which keeps this safe. - Whole numbers from
Math.random(). It returns a floating-point number, soMath.floorturns the scaled value into an index. - In place. Arrays are objects, so the recursive calls and the caller all share the same array.
- The compiler checks nothing at run time. The annotations
number[]andnumberare erased when TypeScript compiles to JavaScript.
Complexity
Let n be the length of nums.
Time: O(n log n) expected. One partition of a range of length m costs O(m). With a random pivot, the splits are balanced often enough that the depth stays around log n, and each level partitions at most n elements in total. The worst case is O(n²), but with a random pivot it is very unlikely.
Space: O(log n) expected, for the recursion stack. No array is copied.
Edge cases and common mistakes
- Empty and one-element arrays.
[]callsquickSort(nums, 0, -1), andleft >= rightreturns at once. This is why the base case uses>=. - Many equal values. This partition uses
<=, so all copies of the pivot value go to the left side. If every element is equal, the pivot always ends up last, one side is always empty, and the work grows liken²whatever the random choice is. In a test, 1,000 equal values took about 500,000 element visits, and 20,000 equal values crashed with aRangeError(call stack exceeded) because the recursion became that deep. With ordinary data that has some duplicates, as in the example, it is fine. - Forgetting to skip the pivot. The recursive calls use
pivot - 1andpivot + 1. Passingpivotinto one of them can leave a range that never shrinks. - Looping to
right - 1. The loop here includesright, because the pivot is moved into place by the scan. If you stop earlier, you must swap it into place yourself after the loop. - Wrong random range.
Math.floor(Math.random() * (right - left))can never pickright, and without addingleftthe index falls outside the range. - Using the built-in
sort()as a model.nums.sort()without a comparator compares as strings, so[10, 9, 1]becomes[1, 10, 9]. The comparisons here use<=on numbers, which is correct.
Testing
[3, 1, 3, 2, 5, 4]gives[1, 2, 3, 3, 4, 5].[]stays[], and[5]stays[5].[2, 1]gives[1, 2].[10, 9, 1]gives[1, 9, 10].[-1, -5, 0, -5]gives[-5, -5, -1, 0].[4, 4, 4, 4]stays[4, 4, 4, 4].