What is Merge Sort?
In computer science, merge sort is an efficient, general-purpose, comparison-based sorting algorithm.
Most implementations produce a stable sort, which means that the order of equal elements is the same in the input and output.
It is a divide and conquers algorithm. In the divide and conquer paradigm, a problem is broken into pieces where each piece still retains all the properties of the larger problem – except its size.
1. .
2. Much More Efficient for small and large data sets.
3. Adaptive that is efficient for the type of data sets that are already substantially sorted.
4. Stable Sorting Algorithm
Define Merge Sorting Function
Now, let’s define a new function named merge-sorting which accepts one parameter which is list we pass as an argument to this function.
So this function is to sort an array or list using a merge sorting algorithm.
As we have discussed above, to solve the original problem, each piece is solved individually and then the pieces are merged back together.
For that, we are going to use recursive calls to a new function named merge which accepts two sorted arrays to form a single sort array.
Now in the merge-sort function, the base condition for our recursive call is that if the length of an array or list is equal to 0 or 1 then simply return the first element of the array.
Otherwise, just divide the array into two equal halves and pass both arrays to recursive calls of merge-sort.
And at last, we are going to call merge function after each recursive call to join both sorted array.
Define Merge Function
Now we are breaking the array until they are divided individually. So what we want is just join the arrays that we passed in a sorted way to this function and then returned the new array as a result.
Complexity
The overall time complexity of Merge is O(nLogn).
The space complexity of Merge-sort is O(n).
This means that this algorithm takes a lot of space and may slow down operations for large data sets.
Define Main Condition
Now, let’s create a main condition where we need to call the above function and pass the list which needs to be sorted.
So let’s manually defined the list which we want to pass as an argument to the function.
Source Code
Output
JS Implementation:
Merge sort divides an array into halves, calls itself for the two halves, and then merges the two halves.
The merge algorithm consists of two functions: the mergeSort function, which takes care of partitioning the arrays, and the merge function, which merges the separate arrays.
The implementation of merge sort is the following, and is the easiest to explain using animations as example:
We invoke the mergeSort function with the array we want to have sorted. The array gets split in two parts: a left, and a right part. Then, we return the merge function with two arguments, where we call the mergeSort function for the left side of the array, and the mergeSort function for the right side of the array.
The mergeSort function gets invoked with the items on the left side of the array, which are 6 and 4. Again, this array gets split in two parts: a left, and a right part. Then, we again return the merge function, where we call the merge sort function for the left side of the array, and the mergeSort function for the right side of the array.
The mergeSort function gets invoked with the items on the left side of the array, which is only the item 6 right now. This means that array.length === 1 returns true, which returns the array.
For the first time, we invoke the mergeSort function for the right side of the array! Again, this is only one item, so array.length === 1 returns true. The array gets returned.
As both arguments returned something, the merge function actually gets called now. The merge function receives two arguments: left and right. In this case, left is 6, and right is 4. In the merge function, we declare 3 variables: a new empty array to which we will push the right values later on, the index on the left side, and the index on the right side.
leftIndex < left.length && rightIndex < right.length returns true: the length of both arrays is 1, and the index is 0. (0 < 1 && 0 < 1). The if-statement, left[leftIndex] < right[rightIndex], returns false:
left is [6], so left[0] is 6, and right is [4], so right[0] is 4! This means that the else-block gets run, and we push right[0] to the results array. The results array is now [4]. We also increment the rightIndex from 0 to 1. This means that now,
leftIndex < left.length && rightIndex < right.length returns false, because 0 < 1 && 1 < 1 is not true. The two arrays get concatenated, and returned.
This means that the mergeSort(left) in the merge function we invoked first, finally returned. The exact same logic now applies to mergeSort(right).
Right now, mergeSort(left) and mergeSort(right) have returned from the very first merge call! left is [4,6] and [1, 5] is right.
The results array, displayed as the yellow box, is by default empty. The index of both the left and the right array are 0, which are displayed with the blue box. left[leftIndex] < right[rightIndex] is 4 < 1 in this case, which returns false. right[rightIndex] gets pushed to the results array, and the rightIndex get incremented by one.
As the rightIndex gets incremented by one, right[1] is now 5. 4 < 5 returns true, so left[leftIndex] gets pushed to the results array.
As the leftIndex gets incremented by one, left[1] is now 6. 6 < 5 returns false, so right[rightIndex] gets pushed to the results array.
The while-condition now returns false, which means that the results array gets returned with the leftover value concatenated. We now have our sorted array!
Best, average and worst: Each partitioning takes O(n) operations, and every partitioning splits the array O(log(n)). This results in O(n log(n)).
Worst space: We save three variables for each element in the array.
