Wiki pic - Graphical example of merge sort. Source.
Merge Function
The merge function that compares and merges left and right halves or array will be common for both recursive and iterative merge sort.
function merge(arr, start, mid, end) {
const aux = []
let i = start,
j = mid + 1
// [0]
while (i <= mid && j <= end) {
// [1]
if (arr[i] < arr[j]) {
aux.push(arr[i])
i++
} else {
aux.push(arr[j])
j++
}
}
// [2]
while (i <= mid) {
aux.push(arr[i])
i++
}
// [3]
while (j <= end) {
aux.push(arr[j])
j++
}
// [4]
for (let i = 0; i < aux.length; i++) {
arr[start + i] = aux[i]
}
}
/*
Notes:
[0] Until we reach either the end of the right array or end of the left array,
keep comparing and pushing items into the aux array
[1] arr[i] < arr[j] will result in an unstable sort.
A stable sort is one which preserves the order of repeated values.
[2] Push leftover values from right array
[3] Push leftover values from left array.
There will only be one side with leftover values
[4] Set values of arr[start...end] = aux[0...n-1]
Space complexity O(n) comes from the aux array
*/Recursive Merge Sort
/*
Time Complexity:
Best, worst and average case - О(nlogn)
Space complexity - O(n)
*/
function mergeSort(arr) {
// [0]
function recurse(start, end) {
if (start >= end) return
const mid = start + Math.floor((end - start) / 2)
recurse(start, mid)
recurse(mid + 1, end)
// [1]
merge(arr, start, mid, end)
return
}
recurse(0, arr.length - 1)
}
/*
Notes:
[0] Recursive function that divides the array and recurses on the
left half and right half and finally merges the left and right halves.
[1] Merge the sorted left and right halves
----------------------------------------------------------------
*/
// Tests
const testCases = [
[
[5, 6, 1, 0, 6, 2],
[0, 1, 2, 5, 6, 6],
],
[
[-1, 6, 2, 100, 0, -11],
[-11, -1, 0, 2, 6, 100],
],
[
[7, 6, 5, 4, 3, 2, 1, 0],
[0, 1, 2, 3, 4, 5, 6, 7],
],
]
for (const test of testCases) {
mergeSort(test[0])
console.log(test[0])
console.log(JSON.stringify(test[0]) === JSON.stringify(test[1]))
}Calculating the Time Complexity of Recursive Merge Sort
Iterative or "Bottom Up" Merge Sort
Merge sort can be solved iteratively in a bottom up way. Instead of recursively dividing the array into two halves and merging when you've reached the bottom, you can use two loops and an interval to keep track of which sections of the array you're merging. You don't recurse to the bottom and then return back from the recursive calls. You just start from the bottom which is why it's called "bottom up" merge sort. Intervals will be multiples of 2 because you'll be doubling the number of elements with each merge.
/*
Time Complexity: Best, worst and average case - О(nlogn)
Space complexity - O(n) (for the auxiliary array only, no stack space required)
*/
function mergeSortIterative(arr) {
let len = arr.length
for (let interval = 1; interval < len; interval *= 2) {
for (let start = 0; start < len - interval; start += interval * 2) {
const mid = Math.min(start + interval - 1, len - 1),
end = Math.min(start + 2 * interval - 1, len - 1)
merge(arr, start, mid, end) //Same merge function we used for recursive merge sort
}
}
return arr
}
/*
Recursive merge sort uses recursive call stack
to keep track of which section of the array we're merging.
Eg. for an array of size 4, the recursive call stack will look like
recurse(3, 3)
recurse(2, 2)
recurse(2, 3) merge(2, 2, 3)
recurse(1, 1)
recurse(0, 0)
recurse(0, 1) merge(0, 0, 1)
recurse(0, 3) merge(0, 1 , 3)
Iterative merge sort uses a variable(interval in this case)
to keep track of which section of the array we're merging.
Eg. For array of size 4, merge calls will look like:
Interval 1
merge(0, 0, 1)
merge(2, 2, 2)
Interval 2
merge(0, 1, 3)
----------------------------------------------------------------------------
*/
const testCases = [
[
[5, 6, 1, 0, 6, 2],
[0, 1, 2, 5, 6, 6],
],
[
[-1, 6, 2, 100, 0, -11],
[-11, -1, 0, 2, 6, 100],
],
[
[7, 6, 5, 4, 3, 2, 1, 0],
[0, 1, 2, 3, 4, 5, 6, 7],
],
]
for (const test of testCases) {
mergeSortIterative(test[0])
console.log(test[0])
console.log(JSON.stringify(test[0]) === JSON.stringify(test[1]))
}