Problem overview
The method sort receives an Array[Int] called nums and sorts it in ascending order, in place, using Merge Sort. It returns Unit, so the caller sees the result in the array it passed in. The budget is O(n log n) time and O(n) extra space.
For [3, 1, 3, 2, 5, 4] the array becomes [1, 2, 3, 3, 4, 5].
Approach: split, sort the halves, merge
Merge Sort rests on one fact: two sorted sequences can be merged into one sorted sequence in a single pass. Compare the front elements, take the smaller, and repeat. That takes time proportional to the total length.
So the algorithm sorts by splitting:
- If the range has a single element, it is already sorted.
- Otherwise split it at the middle, sort each half recursively, and merge the two sorted halves.
Halving a range of n elements takes about log2(n) levels, and every level merges n elements in total. That gives O(n log n), whatever the input looks like. For [3, 1, 3, 2, 5, 4] the first split is [3, 1, 3] and [2, 5, 4]; these become [1, 3, 3] and [2, 4, 5], and the final merge interleaves them into [1, 2, 3, 3, 4, 5].
Here is that last merge in detail. The front elements of [1, 3, 3] and [2, 4, 5] are 1 and 2, so 1 goes first. Then the fronts are 3 and 2, so 2 goes next. Then 3 and 4, so a 3 goes, then the other 3. The left half is now used up, and what remains of the right half, 4 and 5, is already in order, so it is copied to the end.
The merge cannot write straight into the array it reads from, because it would overwrite elements it hasn't compared yet. It writes into a buffer, temp, and copies the finished range back. The buffer is the O(n) extra space.
Step by step
- Declare the buffer as a field,
var temp: Array[Int] = Array[Int](). A Scala field needs an initial value, and it must be avarbecausesortreplaces it. - Allocate it in
sortwithnew Array[Int](nums.length). The last merge covers the whole array, so the buffer must be that long. - Start the recursion with
mergeSort(nums, 0, nums.length - 1). The bounds are inclusive. - Declare
mergeSort(nums, left, right)returningUnit, because it sorts in place. - Base case: if
left == right, return. - Find the middle with
val middle = (left + right) / 2. The halves areleft..middleandmiddle + 1..right. - Sort both halves with two recursive calls.
- Merge them with
mergeSubarrays(nums, left, middle, right). - Write the merge. Declare
var i = leftfor the left half,var j = middle + 1for the right half andvar k = leftfor the position intemp. - Main loop: while both halves have elements (
i <= middle && j <= right), copy the smaller ofnums(i)andnums(j)intotemp(k), advance the index it came from, and advancek. - Leftovers: one half may still have elements. Two more
whileloops copy what remains of the left half and then of the right half. At most one of them does anything, and the remaining elements are already in order. - Copy back: a
forloop overleft to rightsetsnums(i) = temp(i).
The solution in Scala
class Solution {
def mergeSubarrays(nums: Array[Int], left: Int, middle: Int, right: Int): Unit = {
var i = left
var j = middle + 1
var k = left
while (i <= middle && j <= right) {
if (nums(i) < nums(j)) {
temp(k) = nums(i)
i += 1
} else {
temp(k) = nums(j)
j += 1
}
k += 1
}
while (i <= middle) {
temp(k) = nums(i)
i += 1
k += 1
}
while (j <= right) {
temp(k) = nums(j)
j += 1
k += 1
}
for (i <- left to right) {
nums(i) = temp(i)
}
}
def mergeSort(nums: Array[Int], left: Int, right: Int): Unit = {
if (left == right) {
return
}
val middle = (left + right) / 2
mergeSort(nums, left, middle)
mergeSort(nums, middle + 1, right)
mergeSubarrays(nums, left, middle, right)
}
var temp: Array[Int] = Array[Int]()
def sort(nums: Array[Int]): Unit = {
temp = new Array[Int](nums.length)
mergeSort(nums, 0, nums.length - 1)
}
}
Scala details:
varversusval.i,jandkchange as the merge advances, so they arevars.middlenever changes, so it is aval.- No
++. Scala has no increment operator, so the code writesi += 1. toincludes both ends.left to rightcoversrighttoo, whileleft until rightwould stop one short.- Shadowing. In
for (i <- left to right), theiis a new variable that hides the outervar iinside the loop. It works, but a different name would read more clearly. - Early
returnin aUnitmethod.returnwith no value leavesmergeSortat once. Writing the recursion inside anif (left < right) { ... }would avoid it. - Arrays are indexed with parentheses,
temp(k), and assigning to an element istemp(k) = value.
Complexity
Time: O(n log n). The recursion is about log2(n) levels deep. At each level the merges together touch every element a constant number of times: one comparison and copy into temp, and one copy back.
Space: O(n). The buffer holds n integers. The call stack adds O(log n), which is smaller.
Edge cases and common mistakes
- Single element.
[5]hits the base case at once and stays unchanged. - Two elements.
[2, 1]splits into two single elements, and the merge produces[1, 2]. - Duplicates and negatives.
[9, -3, 0, -3, 7, 1, 1]becomes[-3, -3, 0, 1, 1, 7, 9]. - Empty array. This version has no guard for it. The first call is
mergeSort(nums, 0, -1);left == rightis false, the middle is 0, and the call onmiddle + 1..right, that is1..-1, leads tomergeSort(nums, 1, 0), which calls itself with the same arguments forever. The program fails with aStackOverflowError. If empty input matters, testnums.length < 2insortbefore starting. - Buffer too small. Allocating
tempwith fewer thannums.lengthelements fails with anArrayIndexOutOfBoundsExceptionon the final merge. - Forgetting the copy back. If the merged range stays in
temp,numsis never sorted. - Stability. Because the comparison is
nums(i) < nums(j), equal elements are taken from the right half first. For plain integers nobody can tell, but when sorting records by a key,<=would keep equal keys in their original order. - Shared buffer.
tempbelongs to theSolutionobject, so two sorts running at the same time on one object would corrupt each other.
Testing
[3, 1, 3, 2, 5, 4]becomes[1, 2, 3, 3, 4, 5].[5]stays[5].[2, 1]becomes[1, 2].[9, -3, 0, -3, 7, 1, 1]becomes[-3, -3, 0, 1, 1, 7, 9].
