Sort an Array

NeetCode: Sort an Array · LeetCode: 912. Sort an Array · Difficulty: Medium

Given an integer array nums, return it sorted in ascending order. Do not use the built-in sort functions such as Arrays.sort. The solution must run in O(n log n) time with the smallest space complexity possible.

Example

Text

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

Brute force: insertion sort

Grow a sorted prefix one element at a time: take the next element and shift larger prefix elements one step right until it fits. Both versions sort a copy made with clone(), so the caller's array stays unchanged. Each insertion can shift the whole prefix, so a reverse-sorted input costs about n^2 / 2 moves.

Java

import java.util.Arrays;

class Solution {
    public int[] sortArray(int[] nums) {
        int[] a = nums.clone();
        for (int i = 1; i < a.length; i++) {
            int x = a[i];
            int j = i;
            while (j > 0 && a[j - 1] > x) {
                a[j] = a[j - 1];
                j--;
            }
            a[j] = x;
        }
        return a;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(Arrays.toString(s.sortArray(new int[]{5, 2, 3, 1})));
        System.out.println(Arrays.toString(s.sortArray(new int[]{5, 1, 1, 2, 0, 0})));
        System.out.println(Arrays.toString(s.sortArray(new int[]{})));
    }
}

Output

[1, 2, 3, 5]
[0, 0, 1, 1, 2, 5]
[]

Time: O(n^2) worst and average (O(n) if already sorted). Space: O(1) extra.

Optimal: merge sort

Split the array in half, sort each half recursively, then merge the two sorted halves by repeatedly taking the smaller front element. The recursion is log n levels deep and each level does O(n) work merging, giving O(n log n) regardless of input order. Taking from the left half on ties keeps it stable. The method works on index ranges [lo, hi) of one array instead of creating sub-arrays, and mid = lo + (hi - lo) / 2 is the overflow-safe midpoint. System.arraycopy moves the merged range from the buffer back into the array.

Java

import java.util.Arrays;

class Solution {
    public int[] sortArray(int[] nums) {
        int[] a = nums.clone();
        int[] buf = new int[a.length];
        mergeSort(a, buf, 0, a.length);
        return a;
    }

    // Sorts a[lo, hi) using buf as scratch space.
    private void mergeSort(int[] a, int[] buf, int lo, int hi) {
        if (hi - lo <= 1) {
            return;
        }
        int mid = lo + (hi - lo) / 2;
        mergeSort(a, buf, lo, mid);
        mergeSort(a, buf, mid, hi);
        int i = lo, j = mid, k = lo;
        while (i < mid && j < hi) {
            if (a[i] <= a[j]) {
                buf[k++] = a[i++];
            } else {
                buf[k++] = a[j++];
            }
        }
        while (i < mid) {
            buf[k++] = a[i++];
        }
        while (j < hi) {
            buf[k++] = a[j++];
        }
        System.arraycopy(buf, lo, a, lo, hi - lo);
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(Arrays.toString(s.sortArray(new int[]{5, 2, 3, 1})));
        System.out.println(Arrays.toString(s.sortArray(new int[]{5, 1, 1, 2, 0, 0})));
        System.out.println(Arrays.toString(s.sortArray(new int[]{})));
    }
}

Output

[1, 2, 3, 5]
[0, 0, 1, 1, 2, 5]
[]

Time: O(n log n). Space: O(n) for the merge buffer (plus O(log n) recursion depth, which is small enough for any array size).

Heap sort also reaches O(n log n) with O(1) extra space but is not stable. When the values are bounded (the constraints here are -50000 to 50000), counting sort runs in O(n + range): count how many times each value occurs, then write the values out in order. It is not a comparison sort, so it pays off only when the range is small relative to n log n.