Given an integer array nums, sort it in ascending (non-decreasing) order and return the sorted array.
You may not call a built-in sort — implement the sorting yourself. This problem exists to exercise a comparison-based sort (quicksort, mergesort, heapsort, …) from scratch rather than to test whether you know a library function.
Example
Constraints
- 1 <= nums.length <= 5 * 10^4
- -5 10^4 <= nums[i] <= 5 10^4
Intuition
A first pass sorts the way you'd sort a hand of playing cards: grow a sorted prefix one element at a time, sliding each new value left past every already-placed value that's bigger than it.
function sortArray(nums) {
// Grow a sorted prefix nums[0..i-1] one element at a time.
for (let i = 1; i < nums.length; i++) {
const current = nums[i]; // the value being inserted into the sorted prefix
let j = i - 1;
// Shift every larger value in the sorted prefix one slot right...
while (j >= 0 && nums[j] > current) {
nums[j + 1] = nums[j];
j--;
}
// ...then drop current into the gap that shifting opened up.
nums[j + 1] = current;
}
return nums;
}This is O(n²) — each insertion can shift the entire sorted prefix, so a reverse-sorted input does roughly n²/2 shifts. Can we do better?
The key move: pick a pivot value and, in a single pass over the range, split everything ≤ it from everything > it. That one pass drops the pivot into its final sorted position — and, crucially, the two sides can now be sorted completely independently, since every value on the left is already ≤ every value on the right. Recurse into each side and the whole array ends up sorted; this is the Divide and conquer pattern, specialized into quicksort's partition step.
The catch: a fixed pivot choice (always the first or last element) has an input that defeats it — an already-sorted or reverse-sorted array makes every partition peel off just a single element, degrading to O(n²) time and O(n) recursion depth. Randomizing the pivot on every call, as the stored solution does, means no single input can reliably trigger that worst case; the expected running time stays O(n log n) regardless of the input's initial order.
In the stored solution, the region built by "everything ≤ pivot so far" is tracked by a boundary index, while a scan pointer i walks the rest of the range one step at a time; the walkthrough below marks only the pivot directly (as pivot) and narrates boundary/i in the captions, so the names line up when you get to the code. Walking it through:
quicksort([7, 2, 5, 9, 1]) — choose a pivot
The pivot is drawn at random on every call — not fixed to index 0 or the last index — so no single crafted input (like an already-sorted array) can force the O(n²) worst case.
after partitioning around 5
One pass over the range swapped 2 and 1 (≤ 5) ahead of the boundary; 5 has landed in its final sorted position, with the left partition (indices 0–1) holding everything smaller.
7 and 9 (> 5) end up on the other side. Each partition recurses independently — quicksort never has to compare across the two sides again.
after the left partition [2, 1] sorts itself
2 is > 1, so it stays right of the pivot; the left partition finishes as [1, 2]. Both sides are now single elements, so recursion on that half stops.
after the right partition [9, 7] sorts itself — fully sorted
The right partition finishes as [7, 9]. Every partition landed its pivot and never needed to look at the other side — that recursive independence, applied down to single-element base cases, is what turns one partition into a full sort.
Optimization
Randomized quicksort
Classic in-place quicksort, with one twist that matters: the pivot is chosen at random on every partition call, rather than always taking (say) the last element.
Why randomize: a fixed pivot choice has an input that defeats it — e.g. always picking the last element makes an already-sorted or reverse-sorted array degrade to O(n^2) time and O(n) recursion depth, because every partition splits off just one element. Randomizing the pivot means no single input can reliably trigger the bad case; the expected behavior is O(n log n) time and O(log n) recursion depth regardless of the input's initial order.
The partition step (Lomuto scheme here) picks a random index, swaps that value to the end so it can be treated uniformly as "the pivot", then walks the range once, swapping every element <= pivot into a growing prefix. The pivot is swapped into place right after the prefix, splitting the range into "everything <= pivot" and "everything > pivot" — recursing on both sides sorts the whole array.
O(n log n) expected time, O(log n) expected extra space (recursion stack); worst case O(n^2) time is possible but astronomically unlikely with a random pivot.
function sortArray(nums) {
quicksort(nums, 0, nums.length - 1);
return nums;
}
// Sorts nums[low..high] in place (inclusive bounds).
function quicksort(nums, low, high) {
if (low >= high) return; // 0 or 1 elements: already sorted
const pivotIndex = partition(nums, low, high);
quicksort(nums, low, pivotIndex - 1);
quicksort(nums, pivotIndex + 1, high);
}
// Lomuto partition around a randomly chosen pivot. Returns the pivot's final index.
function partition(nums, low, high) {
// Pick a random pivot in [low, high] and move it to the end so the rest of the
// routine can partition against a known position — this is what defeats any
// input crafted to break a fixed pivot choice.
const randomIndex = low + Math.floor(Math.random() * (high - low + 1));
swap(nums, randomIndex, high);
const pivotValue = nums[high];
// boundary tracks the end of the "<= pivot" region built so far.
let boundary = low;
for (let i = low; i < high; i++) {
if (nums[i] <= pivotValue) {
swap(nums, i, boundary);
boundary++;
}
}
// Drop the pivot into place right after everything <= it.
swap(nums, boundary, high);
return boundary;
}
function swap(nums, i, j) {
const temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}Complexity analysis
Time complexity: O(n log n) expected. Here's why:
- Each call to
partitiondoes a single O(k) pass over the k-element range it's given, swapping values around the pivot. - With a randomized pivot, each partition is expected to split its range reasonably evenly, so the recursion is expected to be O(log n) levels deep.
- Every level's partition calls together touch every element once, so each level costs O(n) — O(n) work × O(log n) levels.
So the expected running time is O(n log n). An unlucky sequence of random pivots can still produce lopsided splits, so the worst case remains O(n²) — but with a random pivot on every call, no fixed input can force that case; it only happens by chance, with vanishing probability as n grows.
Space complexity: O(log n) expected. Here's why:
partitionsorts in place — it only swaps elements withinnums, so it allocates no auxiliary array.- The only extra space is the call stack from recursing into each side; its depth tracks how balanced the splits are, which is expected O(log n) with a random pivot.
The output isn't a separate structure (the input array is mutated and returned), and the worst-case call-stack depth — if every partition happened to split off just one element — would be O(n).
Test cases
Beyond the example above, these are worth thinking through before you submit.
| Input | Expected output | Description |
|---|---|---|
| nums = [] | [] | Empty array — nothing to sort. |
| nums = [-9] | [-9] | Single element — already sorted by definition. |
| nums = [4,4] | [4,4] | Smallest all-equal case — no swaps are ever needed. |
| nums = [3,-3,3,-3,0] | [-3,-3,0,3,3] | Duplicates straddling zero — repeated values must land adjacent, on both sides of 0. |
| nums = [5,4,3,2,1] | [1,2,3,4,5] | Reverse-sorted — the classic input that drives a fixed-pivot quicksort toward O(n²); a randomized pivot keeps this fast. |
Try it yourself
Write your solution against the real judge before checking the reference.