Sort an Array

Problem Description

Given an array of integers nums, sort the array in ascending order and return it.

You must solve the problem without using any built-in library functions in O(n log n) time complexity and with the smallest space complexity possible.

Examples

Constraints

• 1 <= nums.length <= 5 * 10⁴
• -5 * 10⁴ <= nums[i] <= 5 * 10⁴

Divide and Conquer Sorting

To achieve a guaranteed O(n log n) time complexity, basic sorting algorithms like Bubble Sort or Insertion Sort (which take O(n²)) are insufficient. Merge Sort solves this using divide-and-conquer. It splits the array into two halves, recursively sorts each half, and merges the sorted halves back together. This divide-and-conquer step guarantees the log n depth of recursion, and the linear merge step at each level ensures the overall runtime remains within O(n log n) bounds.

Solution 1: Merge Sort

Recursively split and merge array slices.

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

    private void mergeSort(int[] nums, int l, int r) {
        if (l >= r) return;
        int mid = l + (r - l) / 2;
        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);
        merge(nums, l, mid, r);
    }

    private void merge(int[] nums, int l, int mid, int r) {
        int[] temp = new int[r - l + 1];
        int i = l, j = mid + 1, k = 0;

        while (i <= mid && j <= r) {
            if (nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
            }
        }

        while (i <= mid) {
            temp[k++] = nums[i++];
        }
        while (j <= r) {
            temp[k++] = nums[j++];
        }

        System.arraycopy(temp, 0, nums, l, temp.length);
    }
}

class Solution:
    def sortArray(self, nums: list[int]) -> list[int]:
        def merge_sort(l: int, r: int):
            if l >= r:
                return
            mid = l + (r - l) // 2
            merge_sort(l, mid)
            merge_sort(mid + 1, r)
            merge(l, mid, r)

        def merge(l: int, mid: int, r: int):
            temp = []
            i, j = l, mid + 1
            while i <= mid and j <= r:
                if nums[i] <= nums[j]:
                    temp.append(nums[i])
                    i += 1
                else:
                    temp.append(nums[j])
                    j += 1
            while i <= mid:
                temp.append(nums[i])
                i += 1
            while j <= r:
                temp.append(nums[j])
                j += 1
            
            for idx in range(len(temp)):
                nums[l + idx] = temp[idx]

        merge_sort(0, len(nums) - 1)
        return nums

#include <vector>

class Solution {
private:
    void merge(std::vector<int>& nums, int l, int mid, int r) {
        std::vector<int> temp(r - l + 1);
        int i = l, j = mid + 1, k = 0;
        while (i <= mid && j <= r) {
            if (nums[i] <= nums[j]) {
                temp[k++] = nums[i++];
            } else {
                temp[k++] = nums[j++];
            }
        }
        while (i <= mid) temp[k++] = nums[i++];
        while (j <= r) temp[k++] = nums[j++];
        for (int idx = 0; idx < temp.size(); idx++) {
            nums[l + idx] = temp[idx];
        }
    }

    void mergeSort(std::vector<int>& nums, int l, int r) {
        if (l >= r) return;
        int mid = l + (r - l) / 2;
        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);
        merge(nums, l, mid, r);
    }

public:
    std::vector<int> sortArray(std::vector<int>& nums) {
        mergeSort(nums, 0, nums.size() - 1);
        return nums;
    }
};

Complexity Analysis

• Time Complexity: O(n log n) in all cases (best, average, worst) as we split the array in half at each step and run a linear merge.
• Space Complexity: O(n) auxiliary space due to the temporary arrays used during the merge process.

Where It Breaks

Merge Sort requires O(n) temporary storage space. In systems with extreme memory constraints, Heap Sort (which runs in O(n log n) time and O(1) space) or Quick Sort (which has an average of O(n log n) but worst-case of O(n²)) is preferred.

Common Mistakes

• Incorrect mid calculation: Using (l + r) / 2 instead of l + (r - l) / 2, which can lead to integer overflow in systems with large array boundaries.
• Off-by-one indices: Setting the right boundary of the first partition as mid - 1 instead of mid, causing elements to be missed during splits.

Frequently Asked Questions

Why not use Quick Sort? Quick Sort is vulnerable to O(n²) worst-case times if the pivot selection is poor and elements are already sorted or identical. Merge Sort guarantees stable O(n log n) timing.

What is stable sorting? Stable sorting algorithms maintain the relative order of identical elements. Merge Sort is stable, whereas algorithms like Quick Sort and Heap Sort are unstable.

← All Problems