Problem 14.1 · Sorting and Divide & ConquerMedium

Sort an Array

What it teaches: Write merge sort and quick sort yourself, and know their trade-offs.

Practise it on judges as “Sort an Array”.

The problem

Sort nums in ascending order without using built-in sorting, in O(n log n) time.

Example 1

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

Example 2

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

Constraints

1 ≤ n ≤ 5 × 10⁴
−5 × 10⁴ ≤ nums[i] ≤ 5 × 10⁴

Pattern clues in the wording

→ Implement a sort
→ O(n log n) required

These clues point to Divide and Conquer: Split the input into halves, solve each half recursively, and combine the results.

Stuck? Take one hint at a time

Solution.java · starter

class Solution {
    public int[] sortArray(int[] nums) {
        return nums;
    }
}

Write your solution locally or in your editor for now. The in-browser runner (Java first, then Python, C++ and more) will run these tests right here.

Test cases

#	Input	Expected
1	nums = [5,2,3,1]	[1,2,3,5]
2	nums = [5,1,1,2,0,0]	[0,0,1,1,2,5]

+ 2 hidden tests the code runner will check

From slow to fast

Approaches

1. Merge sort · O(n log n) always 2. Quick sort with a random pivot · O(n log n) average, O(n²) worst

Merge sort

Time O(n log n) always Space O(n)

Recursively sort halves into a shared temp array and merge.

Approach 1

class Solution {
    public int[] sortArray(int[] nums) {
        mergeSort(nums, new int[nums.length], 0, nums.length - 1);
        return nums;
    }

    private void mergeSort(int[] a, int[] tmp, int lo, int hi) {
        if (lo >= hi) return;
        int mid = (lo + hi) >>> 1;
        mergeSort(a, tmp, lo, mid);
        mergeSort(a, tmp, mid + 1, hi);
        int i = lo, j = mid + 1, k = lo;
        while (i <= mid && j <= hi) tmp[k++] = a[i] <= a[j] ? a[i++] : a[j++];
        while (i <= mid) tmp[k++] = a[i++];
        while (j <= hi) tmp[k++] = a[j++];
        System.arraycopy(tmp, lo, a, lo, hi - lo + 1);
    }
}

Verdict: Predictable and stable.

Quick sort with a random pivot

Time O(n log n) average, O(n²) worst Space O(log n) average stack

Pick a random pivot, swap it to the end, Lomuto-partition, recurse on both sides.

Approach 2

import java.util.concurrent.ThreadLocalRandom;

class Solution {
    public int[] sortArray(int[] nums) {
        quick(nums, 0, nums.length - 1);
        return nums;
    }

    private void quick(int[] a, int lo, int hi) {
        if (lo >= hi) return;
        int p = partition(a, lo, hi);
        quick(a, lo, p - 1);
        quick(a, p + 1, hi);
    }

    private int partition(int[] a, int lo, int hi) {
        swap(a, lo + ThreadLocalRandom.current().nextInt(hi - lo + 1), hi);
        int pivot = a[hi], store = lo;
        for (int i = lo; i < hi; i++) if (a[i] < pivot) swap(a, i, store++);
        swap(a, store, hi);
        return store;
    }

    private void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }
}

Verdict: Fast in practice and in place; the random pivot avoids sorted-input traps.

Before you submit

Edge cases and common mistakes

Test these inputs

Already sorted
All equal (Lomuto degrades; three-way partitioning fixes it)
Negative numbers

Mistakes people make

Fixed pivot on sorted input (O(n²)).
Merge sort allocating arrays in every call.

Interview

Follow-up questions

What sort does Java use?

Command Palette