LeetCode 912 - Sort an Array
The problem asks us to sort an integer array in ascending order without using any built in sorting functions. The result must contain the same elements as the input, but arranged from smallest to largest. The input is an array nums containing integers.
Difficulty: 🟡 Medium
Topics: Array, Divide and Conquer, Sorting, Heap (Priority Queue), Merge Sort, Bucket Sort, Radix Sort, Counting Sort
Solution
Problem Understanding
The problem asks us to sort an integer array in ascending order without using any built in sorting functions. The result must contain the same elements as the input, but arranged from smallest to largest.
The input is an array nums containing integers. These integers may be positive, negative, or zero, and duplicates are allowed. The output is simply the sorted version of that same array.
The important constraint is the required time complexity. The problem explicitly requires an O(n log n) solution, which immediately rules out slower quadratic algorithms such as Bubble Sort, Selection Sort, or Insertion Sort for large inputs. Since the array length can be as large as 5 * 10^4, an O(n^2) algorithm could require billions of operations in the worst case, which would exceed time limits.
The constraints also tell us that the integer values themselves are bounded between -5 * 10^4 and 5 * 10^4. This means non comparison sorting methods like Counting Sort are technically possible. However, the most generally applicable and interview friendly approach is Merge Sort or Heap Sort.
Another important requirement is minimizing extra space usage. Merge Sort guarantees O(n log n) time, but it uses additional memory for merging. Heap Sort achieves O(1) auxiliary space, but the implementation is more complex and typically less intuitive. For this guide, we will use Merge Sort because it is reliable, stable, and easy to reason about.
Several edge cases are important:
- Arrays containing duplicate values, because the algorithm must preserve all occurrences correctly.
- Arrays containing negative numbers, because comparisons must work correctly across positive and negative ranges.
- Arrays of size
1, because they are already sorted and should return immediately. - Already sorted arrays, because the algorithm should still behave correctly.
- Reverse sorted arrays, because they often represent worst case patterns for simpler sorting algorithms.
Approaches
A brute force approach would use a simple quadratic sorting algorithm such as Bubble Sort. Bubble Sort repeatedly compares adjacent elements and swaps them if they are out of order. After enough passes, the largest elements "bubble" to the end of the array.
This works because every inversion in the array is eventually corrected through repeated swaps. However, Bubble Sort requires O(n^2) comparisons in the worst case. With 5 * 10^4 elements, this becomes far too slow.
The key insight for a better solution is that we can divide the array into smaller pieces, sort those smaller pieces recursively, and then efficiently merge the sorted pieces back together. This is the foundation of Merge Sort.
Merge Sort works efficiently because merging two already sorted arrays can be done in linear time. By repeatedly splitting the problem in half, we reduce the number of comparisons dramatically. The recursive splitting creates log n levels, and each level processes all n elements exactly once, leading to O(n log n) total complexity.
| Approach | Time Complexity | Space Complexity | Notes |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | Bubble Sort repeatedly swaps adjacent elements |
| Optimal | O(n log n) | O(n) | Merge Sort recursively divides and merges sorted halves |
Algorithm Walkthrough
Merge Sort Overview
Merge Sort follows the divide and conquer paradigm. The algorithm repeatedly splits the array into smaller subarrays until each subarray contains only one element. A single element is inherently sorted. Then the algorithm merges the smaller sorted subarrays back together in sorted order.
Step by Step Process
- Divide the array into two halves.
We find the midpoint of the current array segment and split it into a left half and a right half. This reduces the problem size at every recursive call. 2. Recursively sort the left half.
The left half may still be unsorted, so we apply the same process again until we eventually reach subarrays of size one. 3. Recursively sort the right half.
The same recursive logic is applied to the right side. 4. Merge the two sorted halves.
Once both halves are sorted, we merge them into a single sorted array. We use two pointers, one for each half.
- Compare the current elements from both halves.
- Place the smaller element into the merged array.
- Move the pointer forward in the half from which the element was taken.
- Continue until one half is exhausted.
- Append any remaining elements from the other half.
- Return the merged sorted array.
After merging, the current recursive call returns a fully sorted segment to its parent call.
Why it works
Merge Sort works because of a simple invariant: whenever we merge two arrays, those arrays are already individually sorted. Since we always choose the smaller front element during merging, the resulting merged array is also sorted. Recursive division guarantees that eventually every subarray becomes trivially sorted, and repeated merging reconstructs the entire array in sorted order.
Python Solution
from typing import List
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
def merge_sort(left: int, right: int) -> None:
if left >= right:
return
mid = (left + right) // 2
merge_sort(left, mid)
merge_sort(mid + 1, right)
merge(left, mid, right)
def merge(left: int, mid: int, right: int) -> None:
temp = []
i = left
j = mid + 1
while i <= mid and j <= right:
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 <= right:
temp.append(nums[j])
j += 1
for index in range(len(temp)):
nums[left + index] = temp[index]
merge_sort(0, len(nums) - 1)
return nums
The implementation begins with the recursive merge_sort function. This function receives the boundaries of the current subarray. If the subarray contains zero or one element, it is already sorted, so the recursion stops immediately.
The midpoint is computed using integer division. The algorithm recursively sorts the left half and right half independently.
After both halves are sorted, the merge function combines them into a single sorted segment. Two pointers track the current position in each half. The smaller value is appended into a temporary array.
Once one half is exhausted, any remaining elements from the other half are appended directly because they are already sorted.
Finally, the merged values are copied back into the original array segment. This ensures the parent recursive call receives a correctly sorted subarray.
Go Solution
func sortArray(nums []int) []int {
var mergeSort func(int, int)
mergeSort = func(left int, right int) {
if left >= right {
return
}
mid := (left + right) / 2
mergeSort(left, mid)
mergeSort(mid+1, right)
merge(nums, left, mid, right)
}
mergeSort(0, len(nums)-1)
return nums
}
func merge(nums []int, left int, mid int, right int) {
temp := []int{}
i := left
j := mid + 1
for i <= mid && j <= right {
if nums[i] <= nums[j] {
temp = append(temp, nums[i])
i++
} else {
temp = append(temp, nums[j])
j++
}
}
for i <= mid {
temp = append(temp, nums[i])
i++
}
for j <= right {
temp = append(temp, nums[j])
j++
}
for k := 0; k < len(temp); k++ {
nums[left+k] = temp[k]
}
}
The Go implementation follows the same recursive Merge Sort strategy as the Python version. Slices in Go naturally support dynamic growth using append, which simplifies temporary array management during merging.
Unlike Python, Go does not support nested named functions directly in the same way, so the recursive helper is declared as a function variable before assignment.
Go slices are references to underlying arrays, so modifications inside helper functions automatically affect the original array.
Worked Examples
Example 1
Input:
[5,2,3,1]
Recursive Splitting
| Step | Subarray |
|---|---|
| Initial | [5,2,3,1] |
| Split | [5,2] and [3,1] |
| Split again | [5],[2],[3],[1] |
Now each subarray has one element, so merging begins.
Merge Process
| Left | Right | Result |
|---|---|---|
| [5] | [2] | [2,5] |
| [3] | [1] | [1,3] |
| [2,5] | [1,3] | [1,2,3,5] |
Final output:
[1,2,3,5]
Example 2
Input:
[5,1,1,2,0,0]
Recursive Splitting
| Step | Subarray |
|---|---|
| Initial | [5,1,1,2,0,0] |
| Split | [5,1,1] and [2,0,0] |
| Split again | [5],[1,1],[2],[0,0] |
| Final split | [5],[1],[1],[2],[0],[0] |
Merge Process
| Left | Right | Result |
|---|---|---|
| [1] | [1] | [1,1] |
| [5] | [1,1] | [1,1,5] |
| [0] | [0] | [0,0] |
| [2] | [0,0] | [0,0,2] |
| [1,1,5] | [0,0,2] | [0,0,1,1,2,5] |
Final output:
[0,0,1,1,2,5]
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(n log n) | The array is split across log n levels, and each level processes all n elements |
| Space | O(n) | Temporary arrays are required during merging |
The recursion depth is log n because the array is repeatedly halved. At each recursion level, merging touches every element exactly once. Multiplying these together gives O(n log n) total time complexity.
The extra space comes from the temporary arrays used during merging. In total, this requires O(n) auxiliary memory.
Test Cases
from typing import List
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
def merge_sort(left: int, right: int) -> None:
if left >= right:
return
mid = (left + right) // 2
merge_sort(left, mid)
merge_sort(mid + 1, right)
merge(left, mid, right)
def merge(left: int, mid: int, right: int) -> None:
temp = []
i = left
j = mid + 1
while i <= mid and j <= right:
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 <= right:
temp.append(nums[j])
j += 1
for index in range(len(temp)):
nums[left + index] = temp[index]
merge_sort(0, len(nums) - 1)
return nums
solution = Solution()
assert solution.sortArray([5,2,3,1]) == [1,2,3,5] # basic unsorted array
assert solution.sortArray([5,1,1,2,0,0]) == [0,0,1,1,2,5] # duplicates
assert solution.sortArray([1]) == [1] # single element
assert solution.sortArray([1,2,3,4]) == [1,2,3,4] # already sorted
assert solution.sortArray([4,3,2,1]) == [1,2,3,4] # reverse sorted
assert solution.sortArray([-3,-1,-2,-5]) == [-5,-3,-2,-1] # negative numbers
assert solution.sortArray([0,0,0]) == [0,0,0] # all identical
assert solution.sortArray([100000,-100000,0]) == [-100000,0,100000] # large magnitude values
assert solution.sortArray([2,1]) == [1,2] # minimal nontrivial case
| Test | Why |
|---|---|
[5,2,3,1] |
Validates standard unsorted input |
[5,1,1,2,0,0] |
Confirms duplicate handling |
[1] |
Verifies base case behavior |
[1,2,3,4] |
Ensures already sorted arrays remain correct |
[4,3,2,1] |
Tests worst ordering for simple sorts |
[-3,-1,-2,-5] |
Confirms negative number handling |
[0,0,0] |
Verifies identical values work correctly |
[100000,-100000,0] |
Tests large magnitude integers |
[2,1] |
Smallest meaningful unsorted array |
Edge Cases
A single element array is an important edge case because recursion must terminate correctly. If the implementation fails to stop when the subarray size becomes one, infinite recursion can occur. The condition if left >= right: prevents this by immediately returning when the segment cannot be split further.
Arrays with duplicate values are another common source of bugs. Some incorrect merge implementations accidentally skip duplicates or overwrite values incorrectly during merging. This implementation preserves duplicates because every element from both halves is copied exactly once into the temporary array.
Negative numbers can also cause issues in some sorting strategies, especially non comparison based methods. Merge Sort relies only on standard integer comparisons, so negative values work naturally without any special handling.
Reverse sorted arrays are particularly important because they expose weaknesses in simpler algorithms like Bubble Sort or Insertion Sort. Merge Sort handles reverse ordering efficiently because its performance depends only on recursive splitting and merging, not on the initial ordering of the input.