Difficulty: MediumSorting

Sort an Array

Problem in Plain English

Rearrange integer values into ascending order without calling a library sort. Compare Quick Sort, Merge Sort and Heap Sort by their time guarantees and memory use.

Problem Statement

Return nums in ascending order, preserving every value and its number of occurrences. Implement the sorting yourself rather than calling a built-in sorting function.

The target is $O(n \log n)$ time with as little extra storage as possible. Randomized Quick Sort illustrates expected performance; Merge Sort and Heap Sort guarantee the time bound. Heap Sort is selected here because it also uses constant auxiliary space.

Constraints

1 <= nums.length <= 50000
-50000 <= nums[i] <= 50000
Do not call a built-in sorting function.

Examples

Example 1

Input: nums = [5, 2, 3, 1]
Output: [1, 2, 3, 5]

The smallest value 1 moves to the front and the largest value 5 moves to the end. The middle values remain in ascending order.

Example 2

Input: nums = [5, 1, 1, 2, 0, 0]
Output: [0, 0, 1, 1, 2, 5]

Both copies of 0 and both copies of 1 are retained. Sorting changes positions, not frequencies.

Example 3

Input: nums = [-50000]
Output: [-50000]

One element is already ordered. No partition, merge or heap extraction is needed.

Example 4

Input: nums = [2, -1, 2, -3, 0]
Output: [-3, -1, 0, 2, 2]

Negative values precede zero and positive values; the two equal 2 values occupy the last two positions.

Intuition

A quadratic scan repeatedly searches the entire unsorted part for its next value. Faster comparison sorts organize those comparisons: Quick Sort groups values around a pivot, Merge Sort combines runs already in order, and Heap Sort keeps the largest remaining value at a tree root. For [5, 2, 3, 1], all three produce [1, 2, 3, 5], but they preserve different invariants and use different storage. Stable sorting preserves the original relative order of equal-valued records; that matters for records with attached data, although equal integers are indistinguishable here.

Approaches

Three-Way Quick Sort

Solution Details

Reveal Three-Way Quick Sort: intuition, complexity, and code

Intuition

Partition around a randomly chosen value so smaller values come before its equal group and larger values come after it. Only the two unequal groups need more work. Random pivots give expected balanced progress, and grouping equals prevents duplicate-heavy input from splitting one equal value at a time. Recurse on the smaller group and handle the larger group in a loop to bound stack memory even when pivots are unlucky.

Step-by-Step Logic

For Example 1 choose pivot 3 from [5, 2, 3, 1]. The random choice may differ on an actual run; this trace fixes the selected value.
Start lt = 0, i = 0, gt = 3. Values before lt are smaller, values from lt through i - 1 equal the pivot, and values after gt are larger.
At i = 0, value 5 is larger: exchange it with value 1 at gt and decrement gt to 2. Keep i = 0 because the incoming 1 is unclassified.
Value 1 is smaller: swap positions i and lt, then advance both to 1. Do the same for value 2, leaving lt = i = 2. Value 3 is equal, so advance only i to 3.
The partition is [1, 2] | [3] | [5]. The right group has one value and needs no recursion. Continue with the left group; choosing pivot 1 leaves [1] | [2]. Return [1, 2, 3, 5].

Why It Works

Each partition maintains four regions: smaller, equal, unknown and larger. A smaller value extends the first region; an equal value extends the second; a larger value extends the last region while its replacement stays unknown. Every iteration shrinks the unknown region, so the loop ends with all values classified. Swaps preserve the input multiset. Equal values are already in their final relation to both outer groups. Sorting those groups therefore sorts the whole range. The smaller-side recursive call and larger-side loop visit exactly the same subproblems as ordinary recursion.

Dry Run

Three-Way Quick Sort: variable states at each step
Action	lt	i	gt	Array / result
Choose pivot 3	0	0	3	[5, 2, 3, 1]
5 greater: swap i with gt	0	0	2	[1, 2, 3, 5]
1 smaller: advance lt and i	1	1	2	[1, 2, 3, 5]
2 smaller: advance lt and i	2	2	2	[1, 2, 3, 5]
3 equal: advance i	2	3	2	[1, 2] / [3] / [5]
Sort [1, 2] with pivot 1	0	1	0	[1] / [2], no ranges of length 2 remain
Return	-	-	-	[1, 2, 3, 5]

Complexity Analysis

Time Complexity

O(n \log n)

Space Complexity

O(\log n)

The time bound is expected over random pivot choices, not a worst-case guarantee: repeatedly extreme pivots can still cost O(n^2). A partition scans its range once; random partitions give expected logarithmic participation per value. Only the smaller unequal group is recursive, and its size is at most half the parent size, so stack space is O(log n) even in the quadratic-time case. Swaps otherwise use constant storage. Equal-only input takes O(n). This sort is unstable. Prefer Heap Sort when a strict worst-case guarantee is required.

Code

Solution.java

1import java.util.concurrent.ThreadLocalRandom;2
3class Solution {4    public int[] sortArray(int[] nums) {5        quickSort(nums, 0, nums.length - 1);6        return nums;7    }8    private void quickSort(int[] a, int lo, int hi) {9        while (lo < hi) {10            int pivot = a[ThreadLocalRandom.current().nextInt(lo, hi + 1)];11            int lt = lo, i = lo, gt = hi;12            while (i <= gt) {13                if (a[i] < pivot) swap(a, lt++, i++);14                else if (a[i] > pivot) swap(a, i, gt--);15                else i++;16            }17            if (lt - lo < hi - gt) {18                quickSort(a, lo, lt - 1);19                lo = gt + 1;20            } else {21                quickSort(a, gt + 1, hi);22                hi = lt - 1;23            }24        }25    }26    private void swap(int[] a, int i, int j) {27        int value = a[i]; a[i] = a[j]; a[j] = value;28    }29}

Hints

Hint 1

Try finding the next smallest value repeatedly; why does rescanning cost quadratic time?

Hint 2

A pivot can classify values, or two sorted runs can be merged by comparing only their heads.

Hint 3

To get a worst-case time bound with constant extra storage, build a max heap inside nums and move its maximum to the end repeatedly.

Edge Cases

A singleton needs no sorting passes and returns unchanged.
All equal values form one Quick Sort equal region; no unequal recursive work remains.
Sorted and reverse-sorted input must not cause linear recursion depth; only the smaller Quick Sort side is recursive.
Merge Sort must handle a final run shorter than width and a missing right run.
Heap Sort must handle a parent with only a left child and restrict every repair to the active prefix.
Negative numbers and the extreme permitted values are compared directly; no offset or counting range is necessary.

Common Mistakes and Interview Tips

Advancing i after swapping a greater-than-pivot value with gt skips the incoming unknown value.
Keeping the pivot as a mutable array position rather than copying its value can change the comparison target during swaps.
Claiming randomized Quick Sort has a guaranteed O(n log n) bound; its worst case is still quadratic.
Recursing into both Quick Sort sides without controlling stack depth can overflow on pathological partitions.
Merging directly into the input without a buffer can overwrite an unread value. Taking the right head on equality also loses stability.
Using a min heap while placing extracted values at the end produces descending order.
Sifting into the fixed suffix after heap extraction breaks already placed maxima. The end index is the exclusive heap size.

Key Takeaway

Choose a sorting invariant to match the actual requirements: randomized partitions for expected speed, stable merging when equal-record order matters, or heap extraction for guaranteed O(n log n) time with constant auxiliary space.