The Merge Sort algorithm is one of the most commonly used sorting algorithms in computer science and is also one of the most efficient. It’s based on the principle of Divide and Conquer, and this technique is the basis of efficient algorithms for many problems.
Explaining the concept
A Divide and Conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.
On a sorting algorithm, the idea is 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 by comparing their items one by one and adding the smaller item first.
At the end of the sorting we concatenate any left variables at the end of our result list . Since we already sorted the arrays, the last element will always be in the correct position.
The concept is fairly easy to understand but one question still remains. How do we reach a state in which we have two sorted arrays? Well, we can achieve that by splitting the array into halves recursively. We do that until we reach a point in which we compare multiple pairs of single-item arrays.
The code below shows how this works.
[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]
You can see how we recursively split the array into smaller arrays until we have only arrays of single items. At that point we start comparing the items one by one and using the above mentioned concatenating method . When the algorithm reaches it’s end, we will have just one sorted array. You can see how the sorting process happens below.
[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,6,7]
[1,2,3,4,5,6,7,8,9]
In other words, we split our array to it’s smallest pieces. After that we can assemble them again but in the correct order.
Merge Sort example
Below you’ll see an implementation in JavaScript. It 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 = []
while (left.length && right.length) {
if (left[0] < right[0]) {
result.push(left.shift())
} else {
result.push(right.shift())
}
}
return [...result, ...left, ...right]
}
console.log(mergeSort([1,9,3,8,6,5,7,4,2])) // Returns ordered array
As you can see in the code, Merge Sort algorithm implementation is pretty straightforward.