#912 Sort an Array

frequently reported atGoogle Amazon Microsoft

the problem

In plain words

Sort an integer array in ascending order without built-in sort functions, in O(n log n) time and with the smallest space you can.

in nums = [5,2,3,1]

out [1,2,3,5]

in nums = [5,1,1,2,0,0]

out [0,0,1,1,2,5]

Duplicates must all be kept.

1 ≤ n ≤ 5·10⁴
-5·10⁴ ≤ nums[i] ≤ 5·10⁴

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternMerge sort & merging sorted runs Three-way partition (Dutch flag)Counting / bucket sort

Any O(n²) sort times out at n = 5·10⁴. You need divide and conquer (merge/quick/heap) — or, because values fit in a range of 10⁵, counting sort.

solutions

From brute force to optimal

Grow a sorted prefix; slide each new value left into place.

For i = 1..n−1, hold key = nums[i].
Shift bigger values right.
Drop key into the gap.

timeO(n²)

Reversed input needs n(n−1)/2 shifts — ~1.25·10⁹ at the max n. TLE.

spaceO(1)

Sorts in place.

javajava.util.*

1class Solution {2    public int[] sortArray(int[] nums) {3        for (int i = 1; i < nums.length; i++) {4            int key = nums[i], j = i - 1;5            while (j >= 0 && nums[j] > key) nums[j + 1] = nums[j--];6            nums[j + 1] = key;7        }8        return nums; // correct, but O(n²) → Time Limit Exceeded at n = 5·10⁴9    }10}

Split in halves, sort each recursively, merge with two pointers.

Allocate one helper array up front.
Recursively sort [lo, mid] and [mid+1, hi].
If a[mid] ≤ a[mid+1] the halves are already in order — skip the merge.
Otherwise copy to aux and merge back, taking left on ties.

timeO(n log n)

log n levels × O(n) merging per level, in every case.

spaceO(n)

The helper array plus O(log n) recursion.

javajava.util.*

1class Solution {2    public int[] sortArray(int[] nums) {3        int[] aux = new int[nums.length];4        sort(nums, aux, 0, nums.length - 1);5        return nums;6    }7 8    private void sort(int[] a, int[] aux, int lo, int hi) {9        if (lo >= hi) return;10        int mid = lo + (hi - lo) / 2;11        sort(a, aux, lo, mid);12        sort(a, aux, mid + 1, hi);13        if (a[mid] <= a[mid + 1]) return; // halves already in order → skip the merge14        for (int k = lo; k <= hi; k++) aux[k] = a[k];15        int i = lo, j = mid + 1;16        for (int k = lo; k <= hi; k++) {17            if (i > mid) a[k] = aux[j++];18            else if (j > hi) a[k] = aux[i++];19            else if (aux[j] < aux[i]) a[k] = aux[j++];20            else a[k] = aux[i++];21        }22    }23}

sim

Watch the merge

loading simulation…

javajava.util.*

1class TopDown {2    static void sort(int[] a) {3        int[] aux = new int[a.length]; // one helper array, reused by every merge4        sort(a, aux, 0, a.length - 1);5    }6 7    private static void sort(int[] a, int[] aux, int lo, int hi) {8        if (lo >= hi) return; // 0 or 1 element is already sorted9        int mid = lo + (hi - lo) / 2;10        sort(a, aux, lo, mid);       // sort the left half11        sort(a, aux, mid + 1, hi);   // sort the right half12        merge(a, aux, lo, mid, hi);13    }14 15    private static void merge(int[] a, int[] aux, int lo, int mid, int hi) {16        for (int k = lo; k <= hi; k++) aux[k] = a[k];17        int i = lo, j = mid + 1;     // i walks the left half, j the right half18        for (int k = lo; k <= hi; k++) {19            if (i > mid) a[k] = aux[j++];               // left used up20            else if (j > hi) a[k] = aux[i++];           // right used up21            else if (aux[j] < aux[i]) a[k] = aux[j++];  // strict < : ties take left → stable22            else a[k] = aux[i++];23        }24    }25}

Random pivot, partition into < | = | >, recurse on the outer parts.

Pick a random pivot.
Dutch-flag partition with lt, i, gt.
Recurse on [lo, lt−1] and [gt+1, hi].

timeO(n log n) expected

Random pivots split well on average; the = block makes all-equal input O(n). Worst case O(n²) is astronomically unlikely.

spaceO(log n) expected

Recursion depth of a balanced split.

javajava.util.*

1class Solution {2    private final Random rnd = new Random();3 4    public int[] sortArray(int[] nums) {5        sort(nums, 0, nums.length - 1);6        return nums;7    }8 9    private void sort(int[] a, int lo, int hi) {10        if (lo >= hi) return;11        int pivot = a[lo + rnd.nextInt(hi - lo + 1)]; // random pivot defeats sorted inputs12        int lt = lo, i = lo, gt = hi;                  // 3-way split defeats duplicates13        while (i <= gt) {14            if (a[i] < pivot) swap(a, lt++, i++);15            else if (a[i] > pivot) swap(a, i, gt--);16            else i++;17        }18        sort(a, lo, lt - 1);  // a[lt..gt] all equal the pivot — already final19        sort(a, gt + 1, hi);20    }21 22    private void swap(int[] a, int i, int j) {23        int t = a[i]; a[i] = a[j]; a[j] = t;24    }25}

sim

Partitioning (Lomuto, 2-way)

loading simulation…

javajava.util.*

1class Lomuto {2    static void sort(int[] a) {3        quickSort(a, 0, a.length - 1);4    }5 6    static void quickSort(int[] a, int lo, int hi) {7        if (lo >= hi) return;8        int p = partition(a, lo, hi); // pivot is now final at index p9        quickSort(a, lo, p - 1);10        quickSort(a, p + 1, hi);11    }12 13    static int partition(int[] a, int lo, int hi) {14        int pivot = a[hi]; // last element as pivot15        int i = lo;        // a[lo..i-1] holds values < pivot16        for (int j = lo; j < hi; j++) {17            if (a[j] < pivot) {18                swap(a, i, j); // grow the "smaller" zone19                i++;20            }21        }22        swap(a, i, hi); // pivot lands between the two zones23        return i;24    }25 26    static void swap(int[] a, int i, int j) {27        int t = a[i]; a[i] = a[j]; a[j] = t;28    }29}

Build a max-heap in place, then repeatedly move the max to the end.

Heapify bottom-up from n/2 − 1 down to 0.
Swap root with the last heap slot, shrink the heap, sift down.

timeO(n log n)

O(n) build + n sift-downs of O(log n).

spaceO(1)

The heap lives inside the array.

javajava.util.*

1class Solution {2    public int[] sortArray(int[] nums) {3        int n = nums.length;4        for (int i = n / 2 - 1; i >= 0; i--) siftDown(nums, i, n);5        for (int end = n - 1; end > 0; end--) {6            int t = nums[0]; nums[0] = nums[end]; nums[end] = t;7            siftDown(nums, 0, end);8        }9        return nums;10    }11 12    private void siftDown(int[] a, int i, int size) {13        while (2 * i + 1 < size) {14            int c = 2 * i + 1;15            if (c + 1 < size && a[c + 1] > a[c]) c++;16            if (a[i] >= a[c]) return;17            int t = a[i]; a[i] = a[c]; a[c] = t;18            i = c;19        }20    }21}

Values lie in [−5·10⁴, 5·10⁴]: count each value, then write them back in order.

count[x + 50000]++ for each x.
Walk values low → high, writing each count times.

timeO(n + k)

k = 100,001 possible values — linear for this input size.

spaceO(k)

The count array.

javajava.util.*

1class Solution {2    public int[] sortArray(int[] nums) {3        final int OFFSET = 50_000;                 // constraint: -5·10⁴ ≤ nums[i] ≤ 5·10⁴4        int[] count = new int[2 * OFFSET + 1];5        for (int x : nums) count[x + OFFSET]++;6        int k = 0;7        for (int v = 0; v < count.length; v++) {8            while (count[v]-- > 0) nums[k++] = v - OFFSET;9        }10        return nums;11    }12}

in the room

How to say it in the interview

talk track

Ask: can I use extra memory? Are there many duplicates? What's the value range?
Pick merge sort as the safe default and say why: guaranteed O(n log n), stable.
Mention quicksort's O(n²) trap on sorted/all-equal input and how a random pivot + 3-way partition fixes it.
Point out that counting sort is legal here because the value range is bounded.

traps

Lomuto quicksort with a fixed pivot TLEs on LeetCode's all-equal and sorted tests.
Allocating a new array inside every merge call — correct but slow and memory hungry.

what they ask next

Follow-ups

Sort a 100 GB file with 1 GB of RAM?

External merge sort: sort 1 GB chunks in memory, write them out, then k-way merge the chunks with a min-heap.

Why does Java use different algorithms for int[] and Integer[]?

Objects need stability (equal keys may be distinguishable); primitives don't, so the faster unstable dual-pivot quicksort is used.

before you submit

Edge cases to test

One element: already sorted, return it.
5·10⁴ equal values: a 2-way (Lomuto) quicksort goes O(n²) here — use a 3-way partition or merge sort.
Sorted or reversed input: a fixed first/last pivot degrades to O(n²) with recursion n levels deep.
Values at both bounds (−5·10⁴ and 5·10⁴): counting sort needs an offset of 50,000.

practise next