912. Sort an Array

MediumView on LeetCode

Array Sorting Divide and Conquer Heap (Priority Queue)

Time: O(n log n)

Space: O(n)

Problem Overview

LeetCode expects O(n log n) sorting.

Intuition

LeetCode expects O(n log n) sorting. Merge sort guarantees O(n log n) worst case and is stable. QuickSort can degrade to O(n²) on sorted or adversarial input unless you randomize pivots — merge sort is the safer interview default here.

Algorithm

1Define MergeSort(arr, lo, hi): if lo >= hi return.
2mid = (lo + hi) / 2. Recurse on [lo, mid] and [mid+1, hi].
3Merge the two sorted halves into a temp buffer with two pointers.
4Copy merged segment back into arr.
5Call MergeSort on full array and return arr.

Example Walkthrough

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

1.Split [5,2|3,1] -> [5|2] and [3|1].
2.Merge to [2,5] and [1,3], then final merge -> [1,2,3,5].

Output: [1, 2, 3, 5]

Common Pitfalls

•Naive Lomuto QuickSort may TLE — prefer merge sort or randomized quicksort.
•Merge step needs O(n) auxiliary space per level.
•In-place merge sort variants exist but standard top-down merge is clearest.

912.cs

// Approach: Merge sort; recursively split array in halves and merge sorted halves.
// Time: O(n log n) Space: O(n)

public class Solution
{
    public int[] SortArray(int[] nums)
    {
        MergeSort(nums, 0, nums.Length - 1);

        return nums;
    }

    private void MergeSort(int[] A, int l, int r)
    {
        if (l >= r)
            return;

        int m = (l + r) / 2;

        MergeSort(A, l, m);
        MergeSort(A, m + 1, r);
        Merge(A, l, m, r);
    }

    private void Merge(int[] A, int l, int m, int r)
    {
        int[] sorted = new int[r - l + 1];
        int i = l, k = 0, j = m + 1;

        while (i <= m && j <= r)
        {
            if (A[i] < A[j])
                sorted[k++] = A[i++];
            else
                sorted[k++] = A[j++];
        }

        while (i <= m)
            sorted[k++] = A[i++];

        while (j <= r)
            sorted[k++] = A[j++];

        Array.Copy(sorted, 0, A, l, sorted.Length);
    }
}

Was this solution helpful?