Problem statement

Given an integer array nums, sort it in ascending order and return it — without using built-in sort functions, in O(n log n) time with the smallest possible extra space.

Implement merge sort, heap sort, or quicksort by hand.

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 <= nums.length <= 40
• -1000 <= nums[i] <= 1000

Hints for Sort an Array

1. Hint 1

   Merge sort guarantees O(n log n) and is stable.

2. Hint 2

   Heap sort achieves O(1) extra space; quicksort needs a good pivot strategy.

How to solve Sort an Array

The task is to write the sort itself. Merge sort is the safest choice under the constraints: it is O(n log n) in the worst case with no dependence on the input's shape, unlike quicksort, whose naive pivot choice degrades to O(n^2) on already-sorted or adversarial data.

Approach

1. An array of length 0 or 1 is already sorted — return it.
2. Split the array at the midpoint into two halves.
3. Sort each half recursively.
4. Merge: walk both sorted halves with one index each, repeatedly taking the smaller front element.
5. When one half runs out, append everything left in the other.

Why it works

Merging two sorted sequences is correct because the smallest unplaced element overall is always at the front of one of the two halves — nothing behind it in its own half is smaller, and the comparison covers the other half. Each level of recursion does O(n) merging work and the depth is log n, giving O(n log n) regardless of input order. Taking the left element on ties (<=) also makes the sort stable.

Complexity

• Time — O(n log n)
• Space — O(n)

Pitfalls

• Do not forget to drain the remaining half after the main merge loop ends — dropping it silently loses elements.
• Use <= rather than < when comparing fronts to keep the sort stable.
• Recursing on a half that is not strictly smaller than the original (an off-by-one at the midpoint) gives infinite recursion.
• Quicksort with a fixed first-element pivot passes small random tests but degrades badly on sorted input; if you go that route, pick the pivot randomly or use median-of-three.

Reference solution

Python

from typing import List

def sortArray(nums: List[int]) -> List[int]:
    if len(nums) <= 1:
        return nums
    mid = len(nums) // 2
    left = sortArray(nums[:mid])
    right = sortArray(nums[mid:])
    out = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i])
            i += 1
        else:
            out.append(right[j])
            j += 1
    out.extend(left[i:])
    out.extend(right[j:])
    return out

Java

public static int[] sortArray(int[] nums) {
    if (nums.length <= 1) return nums.clone();
    int mid = nums.length / 2;
    int[] left = sortArray(Arrays.copyOfRange(nums, 0, mid));
    int[] right = sortArray(Arrays.copyOfRange(nums, mid, nums.length));
    int[] out = new int[nums.length];
    int i = 0, j = 0, p = 0;
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) out[p++] = left[i++];
        else out[p++] = right[j++];
    }
    while (i < left.length) out[p++] = left[i++];
    while (j < right.length) out[p++] = right[j++];
    return out;
}

C++

vector<int> sortArray(vector<int>& nums) {
    if (nums.size() <= 1) return nums;
    int mid = (int) nums.size() / 2;
    vector<int> leftPart(nums.begin(), nums.begin() + mid);
    vector<int> rightPart(nums.begin() + mid, nums.end());
    vector<int> left = sortArray(leftPart);
    vector<int> right = sortArray(rightPart);
    vector<int> out;
    size_t i = 0, j = 0;
    while (i < left.size() && j < right.size()) {
        if (left[i] <= right[j]) out.push_back(left[i++]);
        else out.push_back(right[j++]);
    }
    while (i < left.size()) out.push_back(left[i++]);
    while (j < right.size()) out.push_back(right[j++]);
    return out;
}

JavaScript

var sortArray = function(nums) {
    if (nums.length <= 1) return nums;
    const mid = nums.length >> 1;
    const left = sortArray(nums.slice(0, mid));
    const right = sortArray(nums.slice(mid));
    const out = [];
    let i = 0, j = 0;
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) out.push(left[i++]);
        else out.push(right[j++]);
    }
    while (i < left.length) out.push(left[i++]);
    while (j < right.length) out.push(right[j++]);
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium