# 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

| Item | Meaning |
|---|---|
| Input | An integer array `nums` |
| Output | The same values sorted in ascending order |
| Restriction | Do not use built-in sorting functions |
| Target time | `O(n log n)` |

Function shape:

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

## Examples

Example 1:

```python
nums = [5, 2, 3, 1]
```

Sorted output:

```python
[1, 2, 3, 5]
```

Example 2:

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

Sorted output:

```python
[0, 0, 1, 1, 2, 5]
```

## First Thought: Use Built-in Sort

In normal Python code, we would write:

```python
nums.sort()
return nums
```

or:

```python
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:

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

Use two pointers.

Compare the current values:

```python
1 <= 2
```

Take `1`.

Then compare:

```python
5 <= 2
```

Take `2`.

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

The merged result is:

```python
[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

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n log n)` | There are `log n` levels, and each level merges `n` total elements |
| Space | `O(n)` | Temporary arrays are used during merging |

## Implementation

```python
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:

```python
merge_sort(left, right)
```

This means it sorts indices:

```python
left, left + 1, ..., right - 1
```

The base case is:

```python
if right - left <= 1:
    return
```

A range with at most one element is already sorted.

The middle index splits the range into two halves:

```python
mid = (left + right) // 2
```

Then both halves are sorted recursively:

```python
merge_sort(left, mid)
merge_sort(mid, right)
```

After that, we merge them.

The pointers `i` and `j` scan the two sorted halves:

```python
i = left
j = mid
```

The smaller current value is appended to `merged`:

```python
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:

```python
nums[left:right] = merged
```

## Testing

```python
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:

| Test | Why |
|---|---|
| `[5, 2, 3, 1]` | Main sample |
| `[5, 1, 1, 2, 0, 0]` | Duplicates and zero |
| Single element | Already sorted by definition |
| Increasing input | Already sorted |
| Decreasing input | Worst order visually |
| Negative numbers | Checks integer ordering |
| All equal | Checks duplicates |