LeetCode 912: Sort an Array

Problem Restatement

We are given an integer array nums.

Return the array sorted in ascending order.

The problem requires solving this without using built-in sorting functions, in O(n log n) time, with as little extra space as possible.

Input and Output

Function shape:

def sortArray(nums: list[int]) -> list[int]:
    ...

Examples

Example 1:

nums = [5, 2, 3, 1]

Sorted output:

[1, 2, 3, 5]

Example 2:

nums = [5, 1, 1, 2, 0, 0]

Sorted output:

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

First Thought: Use Built-in Sort

In normal Python code, we would write:

nums.sort()
return nums

or:

return sorted(nums)

But the problem explicitly disallows built-in sorting functions.

So we need to implement a sorting algorithm ourselves.

Key Insight

A reliable way to guarantee O(n log n) time is merge sort.

Merge sort uses divide and conquer:

1. Split the array into two halves.
2. Sort each half.
3. Merge the two sorted halves.

The merge step is linear because both halves are already sorted.

Unlike naive quicksort, merge sort does not degrade to O(n^2) on already sorted input or duplicate-heavy input.

Algorithm

Use recursive merge sort.

For a range nums[left:right]:

1. If the range has length 0 or 1, it is already sorted.
2. Split the range at the middle.
3. Sort the left half.
4. Sort the right half.
5. Merge both sorted halves into a temporary array.
6. Copy the merged values back into nums.

Merge Step

Suppose we need to merge:

left_part = [1, 5, 8]
right_part = [2, 3, 9]

Use two pointers.

Compare the current values:

1 <= 2

Take 1.

Then compare:

5 <= 2

Take 2.

Continue until one side is empty, then copy the rest.

The merged result is:

[1, 2, 3, 5, 8, 9]

Correctness

The base case is correct because any array of length 0 or 1 is already sorted.

For a longer range, the algorithm sorts the left half and the right half recursively.

By the recursive assumption, both halves are sorted before the merge step starts.

The merge step repeatedly chooses the smaller front element from the two sorted halves. Therefore, every appended element is the smallest remaining element among both halves.

So the merged range is sorted and contains exactly the same elements as the original two halves.

By induction on the range length, every recursive call returns a sorted version of its range.

Therefore, the whole array is sorted correctly.

Complexity

Implementation

class Solution:
    def sortArray(self, nums: list[int]) -> list[int]:
        def merge_sort(left: int, right: int) -> None:
            if right - left <= 1:
                return

            mid = (left + right) // 2

            merge_sort(left, mid)
            merge_sort(mid, right)

            merged = []
            i = left
            j = mid

            while i < mid and j < right:
                if nums[i] <= nums[j]:
                    merged.append(nums[i])
                    i += 1
                else:
                    merged.append(nums[j])
                    j += 1

            while i < mid:
                merged.append(nums[i])
                i += 1

            while j < right:
                merged.append(nums[j])
                j += 1

            nums[left:right] = merged

        merge_sort(0, len(nums))
        return nums

Code Explanation

The helper sorts a half-open range:

merge_sort(left, right)

This means it sorts indices:

left, left + 1, ..., right - 1

The base case is:

if right - left <= 1:
    return

A range with at most one element is already sorted.

The middle index splits the range into two halves:

mid = (left + right) // 2

Then both halves are sorted recursively:

merge_sort(left, mid)
merge_sort(mid, right)

After that, we merge them.

The pointers i and j scan the two sorted halves:

i = left
j = mid

The smaller current value is appended to merged:

if nums[i] <= nums[j]:
    merged.append(nums[i])
else:
    merged.append(nums[j])

After one half is exhausted, the remaining values from the other half are copied.

Finally, the sorted values are written back:

nums[left:right] = merged

Testing

def run_tests():
    s = Solution()

    assert s.sortArray([5, 2, 3, 1]) == [1, 2, 3, 5]
    assert s.sortArray([5, 1, 1, 2, 0, 0]) == [0, 0, 1, 1, 2, 5]
    assert s.sortArray([1]) == [1]
    assert s.sortArray([1, 2, 3, 4]) == [1, 2, 3, 4]
    assert s.sortArray([4, 3, 2, 1]) == [1, 2, 3, 4]
    assert s.sortArray([-2, 3, -5, 0]) == [-5, -2, 0, 3]
    assert s.sortArray([2, 2, 2]) == [2, 2, 2]

    print("all tests passed")

run_tests()

Test meaning: