Merge Sort Algorithm Made Easy
Merge Sort is a sorting algorithm that uses the divide and conquer paradigm to sort a given array. Merge sort is efficient and has the time complexity of O(n logn) which is fine for a sorting algorithm and performs much better when compared with sorting algorithms notably Bubble sort.
Easy steps for implementing the Merge sort algorithm
- Write an array merge function: A merge function basically merges 2 arrays into one see : https://uzochukwubenamara.medium.com/javascript-how-to-merge-2-arrays-f69415434ca9 for more details.
The function above basically merges 2 separate arrays into one using a hash table which stores array indexes inside it based on the while loop condition. The i = 0 and j = 0 simply tells the array loop where to start from say 1 for i and 12 for j. A while loop is then ran based on a condition to ensure the arrays are properly stored in the hash table.
2. Writing the MergeSort function: Now that we have a function that simply merges 2 arrays, we can now proceed with writing the mergeSort function.
Note: This heavily relies on Recursion (a function that keeps calling itself until a condition is met). If no base case is defined, an infinite loop would ensue.
Our mergeSort function would have its base case as 1, which implies that if the length of our array equals 1, the recursive mergeSort function should stop, hence, return the sorted array.
As seen above, we separate our array into middle, right and left which is a Divide and Conquer pattern in which an array is separated into 3 parts which would then be worked on. This improves efficiency and reduces operation time O(nlogn) since the number of operations has been decomposed into .
O(logn) : number of decompositions is how many times do we need to split an array to get a single element? i.e. 3 in our case i.e. 1. [23,345,89, 45, 22] → 2. [23, 345], [89], [45,22] → 3. [23], [345] , [89], [45], [22]
O(n) : comparisons per decomposition
O(logn) + O(n) = O(n logn)
In the mergeSort() function above, we then call the mergeSort() function on the right and left arrays recursively in order to put the smaller value of the array to the left and the larger one to the right until the values are sorted appropriately. Once sorted, they need to be merged into one big array. For this, we would use our previous arrayMerge() function to achieve this since all it does is merge separate arrays.
There you go, Merge Sort algorithm made easy! I hope you enjoyed this read. Thanks.
