JavaScript 101: mergeSort(array)
Disclaimer: This material was taught in the JavaScript Algorithms and Data Structures Masterclass on Udemy by Colt Steele, which I highly recommend.
From bubble sort to insertion sort to selection sort, most sorting algorithms take O(n²) Time Complexity on average. If you are looking for a sorting function that is faster, look at mergeSort(). mergeSort() is a combination of, you guessed it, merging and sorting. This article will write out the mergeSort() function for an array of integers in JavaScript using recursion.
Before we get into the mergeSort() function, we have to create a merge function that will serve as a helper to mergeSort(). This merge function will take in two arrays of integers that are sorted from smallest to largest. It will then return one merged array that has sorted all values from both of the arrays from smallest to largest.
This merge function takes into two sorted arrays, arr1 and arr2. It creates an empty results array that it will return at the end of the function. This merge function then iterates through the two arrays, pushing the smallest value from each (which is at the current index i or j, since arr1 and arr2 are sorted already) into the results array until it has iterated through the entire length of arr1 or arr2. Whichever array that has not been iterated through will then push its remaining values into the results array, which is then returned by the merge function.
Below is a rundown of each iteration of the merge function above being run to sort the arrays [2, 15, 60] and [3, 25, 40, 90]:
Great, we now have a merge helper function complete. Let’s get to the mergeSort() function that will take in an array of integers and sort it from its smallest to largest values. This mergeSort() function will use recursion:
The mergeSort(array) function breaks up the array into left and right arrays (using a midpoint to split in half) until the arrays are small enough to have either 1 or 0 elements in the array. As these left and right arrays have lengths greater than 1, they call the mergeSort() function (mergeSort(left) and mergeSort(right)) recursively over and over again, until they become arrays of length 0 or 1. Once the arrays are of 0 or 1 length, they are sorted automatically. We then use the merge helper function on those arrays with other arrays of zero or one element. mergeSort() will then use the merge(left, right) helper method onto the resulting and sorted left and right arrays to create another sorted array from its smallest to its largest value. This process will continue until the array has been merged back together, returning a completely sorted array.
Below is a rundown of how mergeSort() works on an array [24, 10, 76, 73].
First, it is setting up recursive functions: breaking each array into left and right arrays and recursively calling them until the arrays are of length 1.
Second, the calculation of merges, starting with arrays of length 1. We will merge the results until we get one, sorted array:
The time complexity for mergeSort() is O(n log n) — where n is the length of the array — in the best case, average case, and worst case because it is always going to break down the array into smaller arrays of length 1 or 0 no matter what is in the initial array (even if it is sorted already). Each time we decompose the array (run the merge helper functions on the left and right arrays), the number of times we have to split up the array grows by log n (more specifically, log base 2 of n). Every time we use the merge function, there are always n total elements that are going to be compared (as every element of the initial array is compared, whether it is split into half with two arrays or broken up into n arrays of length 1). Since we are doing n operations (per decomposition) log n (number of decompositions) times, the time complexity is O(n log n).
mergeSort(), however, is less efficient for Space Complexity. As we have a larger array, we have to store more arrays with our space, up to n arrays. The Space Complexity of mergeSort() is thus O(n). If space is a consideration, you do not want to use mergeSort(). You would instead want to use bubble sort, insertion sort, or selection sort, which all have a Space Complexity of O(1)
