How Merge Sort Works
Now we will understand the working of merge sort with the help of an example:
Let’s consider another example for merge sort where we have a total of seven (odd) elements in an array and we will sort them in ascending order:
Divide the array into two sub-arrays
Again each array will be divided into two subarrays
Here out of four sub-arrays, one sub-array has only one element but the other three arrays still have more than one element, so we will further divide each of those arrays into two arrays.
Now the first step is complete as each array has only one item in it. Now we will compare the array elements and merge these single item arrays into pairs.
We make a comparison between the array elements of the first two arrays and the last two arrays and shift the smaller values to the left side and greater values to the right side.
A comparison between the elements of the first two arrays and the second two arrays will be conducted. For instance, the first two arrays are [5,7] and [1,4]. 5 will firstly be compared to 1 and then to 4. Afterwards the second element which is 7 will undergo the same procedure and the resulting array will be [1,4,5,7]. Now we will deal with the last two arrays which are [3,6] and [2]. After comparison the array we get will be [2,3,6].
Now we have two arrays; [1,4,5,7] and [2,3,6]. Let’s call them arrayA [1,4,5,7] and arrayB [2,3,6] respectively.
First of all, the first element “1” of arrayA will be compared to the second element “2” of arrayB and the smaller number “1” will be stored in the new sorted array
In the next iteration, “2” will be compared with the next element “4” of arrayA. The smaller one “2” will be stored in the new sorted array.
This time, “4” of arrayA will be compared to the next element “3” of arrayB. As “3” is smaller so it will be inserted into the new sorted array.
This procedure will be done to each element of both arrays and once all elements are compared, the resulting array will be; [1,2,3,4,5,6,7].
Merge Sort in JavaScript
As we have learned how merge sort works now we will code it in JavaScript.
Create a recursive function to divide the unsorted array, we named it “merge_sort”. The recursive function always has a base case to stop the program. We pass the unsorted array to the “merge_sort” function, and inside this function, we find the middle index of the array by dividing the array’s length by 2. Moreover, we utilize the “splice()” method to split the array into sub-arrays.
const midle_index = unsortedArray.length / 2
if(unsortedArray.length < 2){
return unsortedArray
}
const leftArray = unsortedArray.splice(0, midle_index)
return mergeArray(merge_sort(leftArray),merge_sort(unsortedArray))
}
Now, we will discuss the code to merge the two splitting arrays. These splitting arrays are already sorted in the “merge_sort” function, and now we are merging them in the “mergeArrays” function.
let ary = []
while (leftArray.length && rightArray.length) {
if (leftArray[0] < rightArray[0]) {
ary.push(leftArray.shift())
} else {
ary.push(rightArray.shift())
}
}
return [ ...ary, ...leftArray, ...rightArray ]
}
In the above-given function “leftArray” and “rightArray” are the two sorted arrays and we are merging them to obtain a single sorted array. Two methods are used in this example: the “push()” method to add the value at the end of the sorted array and the “shift()” method to delete the value which is selected from the sub-array. Lastly, the console.log() method is used to test the output.
The complete code snippet would go like this:
let ary = []
while (leftArray.length && rightArray.length) {
if (leftArray[0] < rightArray[0]) {
ary.push(leftArray.shift())
} else {
ary.push(rightArray.shift())
}
}
return [ ...ary, ...leftArray, ...rightArray ]
}
function merge_sort(unsortedArray) {
const midle_index = unsortedArray.length / 2
if(unsortedArray.length < 2){
return unsortedArray
}
const leftArray = unsortedArray.splice(0, midle_index)
return mergeArrays(merge_sort(leftArray),merge_sort(unsortedArray))
}
unsortedArray = [5, 7, 1, 4, 6, 3, 2];
console.log(merge_sort(unsortedArray));
Output:
Conclusion:
Merge sort divides a list into sub-lists, and it continues dividing the list until a sub-list gets a single element then it merges all the sub-lists and produces a new sorted list. In this post, we learned the concept of merge sort, then we considered some examples, and finally, we implemented them in JavaScript. We have also explained how the splice method, push method, and shift method works in JavaScript.
