Merge sort is one of the commonly used sorting algorithms in computer science. It’s based on the idea that it’s easier to sort two sorted arrays rather than one unsorted array. Once you have two sorted arrays you can merge them into a single array, comparing their items one by one and adding the smaller item first.

At the end of the sorting any left variables are concatenated at the end of our results list — since the A and B arrays are already sorted this will not cause reordering.

The concept is fairly easy to understand but how do we reach a state in which we have two sorted arrays? Arrays of multiple items can’t be compared until they are sorted! We can achieve this by splitting the array into halves recursively until we reach a point in which we compare multiple pairs of single-item arrays.

             [1,9,3,8,6,5,7,4,2]

[1,9,3,8] [6,5,7,4,2]

[1,9] [3,8] [6,5] [7,4,2]

[1] [9] [3] [8] [6] [5] [7] [4,2]

[1] [9] [3] [8] [6] [5] [7] [4] [2]

This is not the most comprehensive schema ever but you can see how the array is recursively split into smaller and smaller arrays until we reach the state in which we have only arrays containing a single item. At that point we start comparing them one by one and using the above mentioned concatenating method — sort our array.

[1]   [9]   [3]   [8]   [6]   [5]   [7]   [4]   [2]

[1] [9] [3] [8] [6] [5] [7] [2,4]

[1,9] [3,8] [5,6] [2,4,7]

[1,3,8,9] [2,4,5,7,6]

[1,2,3,4,5,6,7,8,9]

In other words, we split our array to it’s smallest pieces and then assemble them again but in the correct order. Here’s an implementation in JavaScript which utilizes the built-in slice function in order to get the parts of the array that we need.

const mergeSort = (arr) => {
if (arr.length === 1) {
return arr
}
const middle = Math.floor(arr.length / 2)
return mergeArray(
mergeSort(arr.slice(0, middle)),
mergeSort(arr.slice(middle))
)
}


const mergeArray = (left, right) => {
let result = []
let indexLeft = 0
let indexRight = 0

while (indexLeft < left.length && indexRight < right.length) {
if (left[indexLeft] < right[indexRight]) {
result.push(left[indexLeft])
indexLeft++
} else {
result.push(right[indexRight])
indexRight++
}
}

return result.concat(left.slice(indexLeft)).concat(right.slice(indexRight))
}

console.log(mergeSort([1,9,3,8,6,5,7,4,2]))

Leave a comment

Leave a Reply