Problem overview
The method sort receives an array of numbers, nums, and must sort it in ascending order using Merge Sort. It returns nothing: the sorting happens inside nums itself. The statement sets a budget of O(n log n) time and O(n) extra space.
For nums = [3, 1, 3, 2, 5, 4] the array becomes [1, 2, 3, 3, 4, 5]. Duplicates, like the two 3s, stay in the result.
Approach: split, sort the halves, merge
Simple sorts such as bubble or insertion sort compare many pairs and take O(n²) time. Merge Sort gets O(n log n) by divide and conquer:
- Split the array in the middle into a left half and a right half.
- Sort each half the same way, recursively. A piece with one element is already sorted, which stops the recursion.
- Merge the two sorted halves into one sorted run.
All the real work happens in the merge. Two sorted halves can be combined in one pass: keep a pointer at the front of each half, copy the smaller of the two front elements to the output, and move that pointer forward. Each element is copied once, so a merge of m elements costs O(m).
The array can be halved about log2(n) times, and every level of the recursion merges n elements in total. That is log n levels of O(n) work. The merge needs somewhere to write its output while it still reads the originals, which is where the O(n) extra space comes from.
Step by step
- Create the buffer. In
sort, setthis.temptonew Array(nums.length). Storing it onthislets all recursive calls share one buffer, and the class needs the declarationtemp: number[];because TypeScript wants every property declared. - Start the recursion with
mergeSort(nums, 0, nums.length - 1). Both bounds are inclusive indices. - Declare
mergeSortwithnums,leftandright, returningvoid. - Base case. When
left === rightthe piece has one element, so return. - Find
middlewithMath.floor((left + right) / 2). Division in TypeScript keeps the fraction, and an index must be whole. - Sort the left half,
lefttomiddle. - Sort the right half,
middle + 1toright. - Merge them with
mergeSubarrays(nums, left, middle, right). This works only because both halves are sorted by now. - Set up three pointers in the merge:
iwalks the left half,jwalks the right half, andkis the next free slot inthis.temp. All three are declared withlet. - Merge while both halves have elements. Compare
nums[i]withnums[j], copy the smaller one intothis.temp[k], advance the pointer of the half it came from, and advancek. - Copy the leftovers. When one half runs out, the other half's remaining elements are already sorted and no smaller than anything written so far, so two short loops append them.
- Copy back. A final loop moves positions
lefttorightfromthis.tempintonums.
The solution in TypeScript
class Solution {
temp: number[];
mergeSubarrays(nums: number[], left: number, middle: number, right: number): void {
let i = left;
let j = middle + 1;
let k = left;
while (i <= middle && j <= right) {
if (nums[i] < nums[j]) {
this.temp[k] = nums[i];
i++;
} else {
this.temp[k] = nums[j];
j++;
}
k++;
}
while (i <= middle) {
this.temp[k] = nums[i];
i++;
k++;
}
while (j <= right) {
this.temp[k] = nums[j];
j++;
k++;
}
for (let i = left; i <= right; i++) {
nums[i] = this.temp[i];
}
}
mergeSort(nums: number[], left: number, right: number): void {
if (left === right) {
return;
}
let middle = Math.floor((left + right) / 2);
this.mergeSort(nums, left, middle);
this.mergeSort(nums, middle + 1, right);
this.mergeSubarrays(nums, left, middle, right);
}
sort(nums: number[]): void {
this.temp = new Array(nums.length);
this.mergeSort(nums, 0, nums.length - 1);
}
}
Some TypeScript details to notice:
- Sorting in place.
sortreturnsvoidand changes the array the caller passed in. Arrays are objects, so the recursive calls all receive a reference to that same array. - Why not the built-in
sort()?nums.sort()with no comparator compares elements as strings, so[10, 9, 1]becomes[1, 10, 9]. Merge Sort compares with<on numbers, which is correct for numbers. - Two variables called
i. Theideclared withletin the finalforheader is a new variable that exists only inside that loop and shadows the earlier one. That is legal, and the earlieriis finished by then anyway. - The buffer starts with empty slots.
new Array(nums.length)has the right length but no values. Each merge writes positionslefttorightbefore reading them, so empty slots are never read. Math.floorand negatives.Math.floor(-0.5)is-1, which matters for the empty array below.
Complexity
Let n be the length of nums.
Time: O(n log n). Each call splits its range in half, so the recursion is about log2(n) levels deep. At each level the merges together touch every element a constant number of times: one comparison pass plus the copy back. Best, average and worst case are all the same, because the split does not depend on the values.
Space: O(n). The buffer holds n numbers. The recursion adds only O(log n) stack frames, so the buffer dominates.
Edge cases and common mistakes
- One element.
[5]stops at the base case and stays as it is. - Two elements.
[2, 1]splits into[2]and[1]and merges to[1, 2]. - Duplicates. When
nums[i]equalsnums[j], the comparison is false, so the right element is copied first. For plain numbers the result is the same either way. Using<=instead would take equal elements from the left half first, which keeps equal items in their original order, the property called stability; that matters when sorting records by a key. - Negative numbers.
[-1, -5, 0, -5]becomes[-5, -5, -1, 0]. The comparison works on values, not on text. - An empty array. With
nums.lengthequal to 0, the first call ismergeSort(nums, 0, -1). Hereleftandrightare not equal, so the base case does not fire,middleisMath.floor(-0.5), which is-1, and the next call ismergeSort(nums, 0, -1)again. The recursion never ends and the program throws aRangeError("Maximum call stack size exceeded"). If empty input is possible, add an early return whennums.length < 2; a base case ofleft >= rightinmergeSortalso covers it. - Splitting wrongly. The halves are
lefttomiddleandmiddle + 1toright. Usingmiddlein both halves repeats an element, and with two elements it recurses on the same range forever. - Forgetting the leftover loops. The main loop stops when one half is empty, so without the two follow-up loops the rest of the other half would be lost.
- Forgetting the copy back. The merged result lives in
this.temp;numsstays unsorted until the last loop copies it over.
Testing
[3, 1, 3, 2, 5, 4]becomes[1, 2, 3, 3, 4, 5].[5]stays[5].[2, 1]becomes[1, 2].[10, 9, 1]becomes[1, 9, 10].[-1, -5, 0, -5]becomes[-5, -5, -1, 0].