Problem overview
Sort an IntArray named nums in ascending order using Merge Sort. The function sort(nums) returns nothing: it rearranges the array it receives. For [3, 1, 3, 2, 5, 4] the array becomes [1, 2, 3, 3, 4, 5].
The lesson asks for O(n log n) time and O(n) extra space. Simple sorts that compare every pair, like bubble or insertion sort, take O(n²). Merge Sort reaches O(n log n) by splitting the work in half again and again, and by combining two sorted halves in a single pass.
Approach
Merge Sort has three ideas:
- An array with one element is already sorted.
- Any longer array can be cut in the middle, and each half sorted on its own by the same method.
- Two sorted halves can be merged into one sorted run by repeatedly taking the smaller of the two front elements.
The splitting makes about log₂(n) levels, and every level does O(n) work in the merges, which gives O(n log n). The merge needs somewhere to put values while it works, because writing straight into nums would overwrite elements that have not been compared yet. So we keep one buffer, temp, as long as the array. That buffer is the O(n) extra space.
Step by step
- Declare the buffer.
tempis a property of the class, typedIntArray. Kotlin requires a property to have a value when the object is created, and the right size is not known untilsortreceives the array.lateinit varpromises the compiler thatsortwill assign it before anyone reads it. - Allocate it in
sort.IntArray(nums.size)is big enough for any merge, since the last merge covers the whole array. - Start the recursion.
mergeSort(nums, 0, nums.size - 1)sorts the range from the first to the last index. Both bounds are inclusive. - Declare
mergeSort. It takes the array and the inclusive boundsleftandright, and returns nothing because it sorts in place. - Base case. If
left == right, the range holds one element, so return. - Find the middle.
(left + right) / 2is integer division. The left half isleft..middleand the right half ismiddle + 1..right. - Sort both halves with two recursive calls.
- Merge. Call
mergeSubarrays(nums, left, middle, right), which relies on both halves being sorted already. - Write the merge. Three indices drive it:
iwalks the left half,jwalks the right half andkis the next free slot intemp. While both halves have elements, copy the smaller front element intotemp[k]and advance its index, then advancek. - Drain the leftovers. When one half runs out, the rest of the other half is already sorted and is at least as large as everything copied so far, so two simple loops copy it over.
- Copy back. Copy
temp[left..right]intonums, so the caller sees the merged range.
The solution in Kotlin
class Solution {
fun mergeSubarrays(nums: IntArray, left: Int, middle: Int, right: Int) {
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++
} else {
temp[k] = nums[j]
j++
}
k++
}
while (i <= middle) {
temp[k] = nums[i]
i++
k++
}
while (j <= right) {
temp[k] = nums[j]
j++
k++
}
for (i in left..right) {
nums[i] = temp[i]
}
}
fun mergeSort(nums: IntArray, left: Int, right: Int) {
if (left == right) {
return
}
val middle = (left + right) / 2
mergeSort(nums, left, middle)
mergeSort(nums, middle + 1, right)
mergeSubarrays(nums, left, middle, right)
}
lateinit var temp: IntArray
fun sort(nums: IntArray) {
temp = IntArray(nums.size)
mergeSort(nums, 0, nums.size - 1)
}
}
Kotlin details worth knowing:
lateinit. It works only onvarproperties of non-primitive types, andIntArrayqualifies. Readingtempbefore it is assigned throwsUninitializedPropertyAccessExceptionwith the messagelateinit property temp has not been initialized. Heresortalways assigns it first.- Member order doesn't matter.
mergeSubarraysusestempbefore the line that declares it. Inside a class, Kotlin lets functions refer to properties declared further down. - The loop variable shadows
i. Infor (i in left..right)theiis a new variable that exists only inside the loop and hides the outervar i. The rangeleft..rightincludes both ends. Aforloop variable is aval, so it can't be assigned inside the loop. <or<=. Withnums[i] < nums[j], equal elements are taken from the right half first. For plain integers the result is the same. Using<=keeps equal elements in their original order, which matters when you sort records by a key.- Integer division. Dividing two
Intvalues drops the fraction, so(0 + 5) / 2is 2.
Complexity
Time: O(n log n). Each recursion level splits ranges in half, so there are about log₂(n) levels. At one level the merges together touch each element a constant number of times, which is O(n). Multiply the two. Sorted, reversed and random input all cost O(n log n).
Space: O(n). The temp buffer holds n integers. The recursion adds O(log n) stack frames, which is smaller and doesn't change the total.
Edge cases and common mistakes
- Duplicates.
[3, 1, 3, 2, 5, 4]sorts to[1, 2, 3, 3, 4, 5]. Equal values go through theelsebranch and nothing is lost.[0, -5, 12, -5, 3]sorts to[-5, -5, 0, 3, 12], so negative numbers work too. - One element. The base case returns immediately and the array is unchanged.
- Empty array. This is a weak spot of the code. For an empty array the call is
mergeSort(nums, 0, -1). Hereleft == rightis false,(0 + -1) / 2is 0 because Kotlin division truncates toward zero, and the calls never reach a range that stops them, so the program ends with aStackOverflowError. If empty input matters to you, add a check such asif (nums.size < 2) returnat the top ofsort. - Forgetting to copy back. If the merged values stay in
temp, the next merge reads stale data fromnums. - Merging unsorted halves. The merge is correct only when both halves are sorted, which is why the recursive calls come before it.
- Shrinking the buffer. A
tempshorter thannumsfails withArrayIndexOutOfBoundsExceptionin the last merge.
Testing
[3, 1, 3, 2, 5, 4]becomes[1, 2, 3, 3, 4, 5].[7]stays[7].[0, -5, 12, -5, 3]becomes[-5, -5, 0, 3, 12].- An array of 100000 numbers comes out in order after a single call.