Sort an Array (Merge Sort) medium
Description
Given an array of integers nums, sort the array in ascending order without using any built-in functions in O(n log n) time and with the smallest space complexity possible.
Examples
> Case 1:
nums = [5, 2, 3, 1]
Output: [1, 2, 3, 5]
> Case 2:
nums = [5, 1, 1, 2, 0, 0]
Output: [0, 0, 1, 1, 2, 5]Constraints
1 <= nums.length <= 5 × 10^4-5 × 10^4 <= nums[i] <= 5 × 10^4
State design
The canonical D&C algorithm:
- Divide: halve the array.
- Conquer: recursively sort each half.
- Combine: merge the two sorted halves.
Recurrence: T(n) = 2 T(n / 2) + O(n) → O(n log n).
Code — top-down merge sort
The <= in the merge tie-break makes the sort stable. Equal elements from the left half are placed before equal elements from the right half, preserving their original order. Use < and the sort is no longer stable — still correct, but loses a useful property.
Code — bottom-up (iterative) merge sort
Pretty for production: no recursion, easier to reason about cache.
def sort_array(nums):
n = len(nums)
size = 1
while size < n:
for lo in range(0, n, 2 * size):
mid = min(lo + size - 1, n - 1)
hi = min(lo + 2 * size - 1, n - 1)
merge(nums, lo, mid, hi)
size *= 2
return numsSame O(n log n) time, same O(n) auxiliary space, no recursion stack.
Analysis
- Time:
O(n log n). - Space:
O(n)for the merge buffer.O(log n)recursion stack on top.
Compare to quicksort: same average time, worse space, worse constant factors, but stable and predictable worst case (no O(n²) worst case).
Same skin
- Count Inversions — same algorithm, count during merge.
- Count of Smaller Numbers After Self — merge sort with index tracking.
- Reverse Pairs — merge sort with a separate count step.
- Sort a Linked List — merge sort with linked-list splitting (no extra
O(n)space).