LeetCode 912: Sort an Array (Top-Down Merge Sort with Stable O(n log n))
LeetCode 912SortingMerge SortToday we solve LeetCode 912 - Sort an Array.
Source: https://leetcode.com/problems/sort-an-array/
English
Problem Summary
Given an integer array nums, sort it in ascending order and return the sorted array. The expected time complexity is O(n log n).
Key Insight
Merge sort guarantees O(n log n) in worst case by recursively splitting into halves and merging sorted halves. It avoids quicksort's worst-case O(n^2) behavior on adversarial inputs.
Brute Force and Limitations
Brute force choices like bubble sort or insertion sort are simple but degrade to O(n^2), which is too slow for large constraints.
Optimal Algorithm Steps (Top-Down Merge Sort)
1) Allocate one temp array with same size as nums.
2) Recursively sort left half and right half.
3) Merge two sorted halves with two pointers into temp.
4) Copy merged segment back to nums.
Complexity Analysis
Time: O(n log n).
Space: O(n) auxiliary array + recursion stack.
Common Pitfalls
- Midpoint overflow in some languages (prefer l + (r - l) / 2).
- Forgetting to copy merged range back into original array.
- Wrong pointer bounds when one half is exhausted.
- Reallocating temp array each recursion (unnecessary overhead).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public int[] sortArray(int[] nums) {
int[] temp = new int[nums.length];
mergeSort(nums, temp, 0, nums.length - 1);
return nums;
}
private void mergeSort(int[] a, int[] temp, int l, int r) {
if (l >= r) return;
int m = l + (r - l) / 2;
mergeSort(a, temp, l, m);
mergeSort(a, temp, m + 1, r);
merge(a, temp, l, m, r);
}
private void merge(int[] a, int[] temp, int l, int m, int r) {
int i = l, j = m + 1, k = l;
while (i <= m && j <= r) {
if (a[i] <= a[j]) temp[k++] = a[i++];
else temp[k++] = a[j++];
}
while (i <= m) temp[k++] = a[i++];
while (j <= r) temp[k++] = a[j++];
for (int p = l; p <= r; p++) a[p] = temp[p];
}
}func sortArray(nums []int) []int {
temp := make([]int, len(nums))
var mergeSort func(int, int)
mergeSort = func(l, r int) {
if l >= r {
return
}
m := l + (r-l)/2
mergeSort(l, m)
mergeSort(m+1, r)
i, j, k := l, m+1, l
for i <= m && j <= r {
if nums[i] <= nums[j] {
temp[k] = nums[i]
i++
} else {
temp[k] = nums[j]
j++
}
k++
}
for i <= m {
temp[k] = nums[i]
i++
k++
}
for j <= r {
temp[k] = nums[j]
j++
k++
}
for p := l; p <= r; p++ {
nums[p] = temp[p]
}
}
if len(nums) > 1 {
mergeSort(0, len(nums)-1)
}
return nums
}class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
vector<int> temp(nums.size());
mergeSort(nums, temp, 0, (int)nums.size() - 1);
return nums;
}
void mergeSort(vector<int>& a, vector<int>& temp, int l, int r) {
if (l >= r) return;
int m = l + (r - l) / 2;
mergeSort(a, temp, l, m);
mergeSort(a, temp, m + 1, r);
merge(a, temp, l, m, r);
}
void merge(vector<int>& a, vector<int>& temp, int l, int m, int r) {
int i = l, j = m + 1, k = l;
while (i <= m && j <= r) {
if (a[i] <= a[j]) temp[k++] = a[i++];
else temp[k++] = a[j++];
}
while (i <= m) temp[k++] = a[i++];
while (j <= r) temp[k++] = a[j++];
for (int p = l; p <= r; ++p) a[p] = temp[p];
}
};class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
temp = [0] * len(nums)
def merge_sort(l: int, r: int) -> None:
if l >= r:
return
m = l + (r - l) // 2
merge_sort(l, m)
merge_sort(m + 1, r)
i, j, k = l, m + 1, l
while i <= m and j <= r:
if nums[i] <= nums[j]:
temp[k] = nums[i]
i += 1
else:
temp[k] = nums[j]
j += 1
k += 1
while i <= m:
temp[k] = nums[i]
i += 1
k += 1
while j <= r:
temp[k] = nums[j]
j += 1
k += 1
for p in range(l, r + 1):
nums[p] = temp[p]
if len(nums) > 1:
merge_sort(0, len(nums) - 1)
return numsvar sortArray = function(nums) {
const temp = new Array(nums.length);
const mergeSort = (l, r) => {
if (l >= r) return;
const m = l + ((r - l) >> 1);
mergeSort(l, m);
mergeSort(m + 1, r);
let i = l, j = m + 1, k = l;
while (i <= m && j <= r) {
if (nums[i] <= nums[j]) temp[k++] = nums[i++];
else temp[k++] = nums[j++];
}
while (i <= m) temp[k++] = nums[i++];
while (j <= r) temp[k++] = nums[j++];
for (let p = l; p <= r; p++) nums[p] = temp[p];
};
if (nums.length > 1) mergeSort(0, nums.length - 1);
return nums;
};中文
题目概述
给定整数数组 nums，将其按升序排序并返回。题目期望的时间复杂度为 O(n log n)。
核心思路
使用归并排序：递归把数组拆成左右两半，分别有序后再线性合并。该方法最坏时间复杂度稳定为 O(n log n)，不会像某些快速排序实现那样退化到 O(n^2)。
基线解法与不足
冒泡排序、插入排序等 O(n^2) 方法实现直观，但在大输入规模下会超时，不适合作为本题主解。
最优算法步骤（自顶向下归并）
1）预先创建一个和 nums 等长的临时数组。
2）递归排序左半区间与右半区间。
3）双指针线性合并两个有序区间到临时数组。
4）将合并结果回写到原数组对应区间。
复杂度分析
时间复杂度：O(n log n)。
空间复杂度：O(n)（临时数组）+ 递归栈。
常见陷阱
- 中点计算写成 (l + r) / 2 可能在部分语言溢出。
- 合并后忘记回写到原数组。
- 某一半耗尽后，尾部元素补拷贝不完整。
- 每层递归都新建临时数组，导致额外开销。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public int[] sortArray(int[] nums) {
int[] temp = new int[nums.length];
mergeSort(nums, temp, 0, nums.length - 1);
return nums;
}
private void mergeSort(int[] a, int[] temp, int l, int r) {
if (l >= r) return;
int m = l + (r - l) / 2;
mergeSort(a, temp, l, m);
mergeSort(a, temp, m + 1, r);
merge(a, temp, l, m, r);
}
private void merge(int[] a, int[] temp, int l, int m, int r) {
int i = l, j = m + 1, k = l;
while (i <= m && j <= r) {
if (a[i] <= a[j]) temp[k++] = a[i++];
else temp[k++] = a[j++];
}
while (i <= m) temp[k++] = a[i++];
while (j <= r) temp[k++] = a[j++];
for (int p = l; p <= r; p++) a[p] = temp[p];
}
}func sortArray(nums []int) []int {
temp := make([]int, len(nums))
var mergeSort func(int, int)
mergeSort = func(l, r int) {
if l >= r {
return
}
m := l + (r-l)/2
mergeSort(l, m)
mergeSort(m+1, r)
i, j, k := l, m+1, l
for i <= m && j <= r {
if nums[i] <= nums[j] {
temp[k] = nums[i]
i++
} else {
temp[k] = nums[j]
j++
}
k++
}
for i <= m {
temp[k] = nums[i]
i++
k++
}
for j <= r {
temp[k] = nums[j]
j++
k++
}
for p := l; p <= r; p++ {
nums[p] = temp[p]
}
}
if len(nums) > 1 {
mergeSort(0, len(nums)-1)
}
return nums
}class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
vector<int> temp(nums.size());
mergeSort(nums, temp, 0, (int)nums.size() - 1);
return nums;
}
void mergeSort(vector<int>& a, vector<int>& temp, int l, int r) {
if (l >= r) return;
int m = l + (r - l) / 2;
mergeSort(a, temp, l, m);
mergeSort(a, temp, m + 1, r);
merge(a, temp, l, m, r);
}
void merge(vector<int>& a, vector<int>& temp, int l, int m, int r) {
int i = l, j = m + 1, k = l;
while (i <= m && j <= r) {
if (a[i] <= a[j]) temp[k++] = a[i++];
else temp[k++] = a[j++];
}
while (i <= m) temp[k++] = a[i++];
while (j <= r) temp[k++] = a[j++];
for (int p = l; p <= r; ++p) a[p] = temp[p];
}
};class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
temp = [0] * len(nums)
def merge_sort(l: int, r: int) -> None:
if l >= r:
return
m = l + (r - l) // 2
merge_sort(l, m)
merge_sort(m + 1, r)
i, j, k = l, m + 1, l
while i <= m and j <= r:
if nums[i] <= nums[j]:
temp[k] = nums[i]
i += 1
else:
temp[k] = nums[j]
j += 1
k += 1
while i <= m:
temp[k] = nums[i]
i += 1
k += 1
while j <= r:
temp[k] = nums[j]
j += 1
k += 1
for p in range(l, r + 1):
nums[p] = temp[p]
if len(nums) > 1:
merge_sort(0, len(nums) - 1)
return numsvar sortArray = function(nums) {
const temp = new Array(nums.length);
const mergeSort = (l, r) => {
if (l >= r) return;
const m = l + ((r - l) >> 1);
mergeSort(l, m);
mergeSort(m + 1, r);
let i = l, j = m + 1, k = l;
while (i <= m && j <= r) {
if (nums[i] <= nums[j]) temp[k++] = nums[i++];
else temp[k++] = nums[j++];
}
while (i <= m) temp[k++] = nums[i++];
while (j <= r) temp[k++] = nums[j++];
for (let p = l; p <= r; p++) nums[p] = temp[p];
};
if (nums.length > 1) mergeSort(0, nums.length - 1);
return nums;
};
Comments