Problem overview
The method Sort receives an int[] named nums and must sort it in ascending order using Merge Sort. It returns nothing: the array itself is rearranged in place. For nums = [3, 1, 3, 2, 5, 4], the array ends up as [1, 2, 3, 3, 4, 5]. Duplicates are fine, and both 3s stay.
The lesson asks for O(n log n) time and O(n) extra space. Simple sorts that compare every element with every other one take O(n²), so this lesson needs a different idea.
Approach: split, sort the halves, merge
Merge Sort is a divide and conquer algorithm. It rests on two observations:
- An array with one element is already sorted.
- Two sorted sequences can be combined into one sorted sequence in a single pass, because the smallest remaining value is always at the front of one of them.
So the algorithm cuts the array in half, sorts each half by calling itself, and then merges the two sorted halves. The recursion keeps halving until the pieces have one element, which is where the sorting actually "starts", and the merges then rebuild larger and larger sorted pieces on the way back up.
Take [3, 1, 3, 2, 5, 4]. It splits into [3, 1, 3] and [2, 5, 4]. The left half becomes [1, 3, 3] and the right half becomes [2, 4, 5]. Merging compares the fronts: 1 against 2 picks 1, then 3 against 2 picks 2, then 3 against 4 picks 3, then 3 against 4 picks 3, and the right half supplies 4 and 5. The result is [1, 2, 3, 3, 4, 5].
The merge needs somewhere to put values while it works, because writing straight into nums would overwrite values that haven't been read yet. That scratch space is the auxiliary array, and it is where the O(n) extra space comes from.
Step by step
- Declare the buffer as a field.
int[] tempsits aboveSort, at class level, so every recursive call can reach it without receiving it as a parameter. - Allocate it once in
Sort. It has the same length asnums, because the final merge covers the whole array. Allocating once avoids creating a new array in every recursive call. - Start the recursion.
MergeSort(nums, 0, nums.Length - 1)sorts the whole array. Both bounds are inclusive. - Declare
MergeSort. It takes the array and the inclusive boundsleftandrightof the part it must sort. - Stop at one element. If
left == right, the part is already sorted, so the method returns. - Find the middle.
(left + right) / 2is anintdivision, which drops the fraction. The left half islefttomiddleand the right half ismiddle + 1toright. - Sort both halves recursively. After these two calls, each half is sorted. Trusting that is the key to writing recursion.
- Merge them.
MergeSubarrays(nums, left, middle, right)combines the two sorted halves into a sortedlefttoright. - Write
MergeSubarrays. Three indexes drive it:ireads the left half,jreads the right half andkwrites intotemp. - Compare while both halves have values. Copy the smaller front value into
temp[k], advance the index of the half it came from, and advancek. - Drain what is left. When one half runs out, the other half's remaining values are already sorted and all at least as large as everything copied so far, so they are copied over as they are. Only one of the two drain loops does any work.
- Copy back. A last loop writes
temp[left..right]intonums. The loop reuses the existingi, because declaring a secondiin the same method would not compile.
The solution in C#
class Solution {
public void MergeSubarrays(int[] nums, int left, int middle, int right) {
int i = left;
int j = middle + 1;
int 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 (i = left; i <= right; i++) {
nums[i] = this.temp[i];
}
}
public void MergeSort(int[] nums, int left, int right) {
if (left == right) {
return;
}
int middle = (left + right) / 2;
this.MergeSort(nums, left, middle);
this.MergeSort(nums, middle + 1, right);
this.MergeSubarrays(nums, left, middle, right);
}
int[] temp;
public void Sort(int[] nums) {
this.temp = new int[nums.Length];
this.MergeSort(nums, 0, nums.Length - 1);
}
}
The C# details worth a closer look:
- Arrays are reference types.
Sort,MergeSortandMergeSubarraysall receive the same array object, so writingnums[i] = ...changes the caller's array. That is why every method returnsvoid. - The field has no modifier. A class member without an access modifier is
private, which is fine here because onlySolutionusestemp. BeforeSortruns,tempisnull;Sortgives it a real array first. this.is optional.this.tempandtempmean the same thing. Writingthis.only makes it plain that the name is a field and not a local variable.- Reusing a loop variable.
for (i = left; ...)has no type, so it continues with theint ideclared at the top. Writingfor (int i = left; ...)would be a compile error here, because a local variable can't reuse the name of one still in scope. - Short-circuit
&&. Ini <= middle && j <= right, the right side is only evaluated when the left side is true. The loop condition therefore never touches an index it shouldn't.
Complexity
Time: O(n log n). Halving an array of length n until single elements remain takes about log n levels. At every level the merges together touch each element a constant number of times (one comparison pass and one copy back), which is O(n) per level. The total is O(n) multiplied by O(log n) levels. The best, average and worst cases all cost the same, because the algorithm never looks at how ordered the input already is.
Space: O(n). The temp array holds n integers. The recursion adds a stack that is only about log n calls deep, because each call works on half the range, so the buffer dominates.
Edge cases and common mistakes
- One element.
left == righton the first call, so the method returns at once and the array is unchanged. - An empty array. The first call is
MergeSort(nums, 0, -1), andleft == rightis false. The middle is(0 + -1) / 2, which is 0, because integer division truncates toward zero. The right half is then(1, -1), whose middle is 0 again, and that leads to the call(1, 0), which keeps calling itself with the same bounds. The recursion never ends and .NET stops the program with a stack overflow. A line such asif (nums.Length < 2) return;at the start ofSortavoids it. - Duplicates. With
nums[i] < nums[j], an equal pair takes the right-hand value first, which does no harm for plain integers. Writing<=would take the left-hand value first, which makes the sort stable: equal elements keep their original order. That matters when sorting records by a key, not when sorting integers. - Forgetting the drain loops. Without them, values left over in one half never reach
temp, and the copy back writes stale data intonums. - Forgetting
k++or an index increment. The loop then runs forever or keeps overwriting one slot oftemp. - Copying back the whole buffer. Only
lefttorightwas merged. Copying other positions would overwrite parts ofnumsthat this call doesn't own. - Allocating the buffer inside every merge. It works but creates many short-lived arrays. A single field, allocated once, is cheaper.
Testing
[3, 1, 3, 2, 5, 4]becomes[1, 2, 3, 3, 4, 5].[7]stays[7].[5, 4, 3, 2, 1, 0, -1]becomes[-1, 0, 1, 2, 3, 4, 5], a reversed input.- Already sorted and all-equal arrays come out unchanged, since the merge only copies values.