#912
Sort an Array
Medium Merge sort
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Sort an integer array in ascending order in O(n log n) without built-in sort functions.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: sort in O(n log n) without library sort.
Why this works: merge sort always splits evenly, so it never degrades like a naive quicksort on sorted input.
Example: [5, 2, 3, 1]
split → [5, 2] [3, 1]sort halves → [2, 5] [1, 3]merge → [1, 2, 3, 5]
✦Hints open one at a time
Merge sort: split in half, sort each half, merge.
Merging two sorted halves takes one pass with two pointers.
Allocate one temp array up front instead of one per call.
↗Approach
Recursive merge sort with a shared buffer. It's stable and always O(n log n), unlike a naive quicksort that can hit O(n²) on sorted or repeated input (which LeetCode tests).
</>Solution (Java)
class Solution {
public int[] sortArray(int[] nums) {
mergeSort(nums, new int[nums.length], 0, nums.length - 1);
return nums;
}
private void mergeSort(int[] a, int[] tmp, int lo, int hi) {
if (lo >= hi) return;
int mid = (lo + hi) >>> 1;
mergeSort(a, tmp, lo, mid);
mergeSort(a, tmp, mid + 1, hi);
int i = lo, j = mid + 1, k = lo;
while (i <= mid && j <= hi) tmp[k++] = a[i] <= a[j] ? a[i++] : a[j++]; // <= keeps it stable
while (i <= mid) tmp[k++] = a[i++];
while (j <= hi) tmp[k++] = a[j++];
System.arraycopy(tmp, lo, a, lo, hi - lo + 1);
}
}!Common mistake
Using quicksort with the first element as pivot — it times out on already-sorted input.
Complexity
- Time: O(n log n).
- Space: O(n).
Topic: Sorting
🎬 Episodes 24–28: video coming soon