Divide and Recurse Over an Array with Merge Sort in JavaScript
Merge sort is a "divide and conquer" algorithm. That is, we break the array down into smaller arrays that are easier and faster to sort; then we stitch the results of calling merge sort on these smaller arrays back together to get our final sorted list.
This is a recursive algorithm, which dramatically improves the efficiency of our sort compared to bubble or insertion sort. The worst case scenario for our list is O(n log(n)), that is, we must go through every item at least once, hence the first n, but with each recursive call we operate on half the data set. This means that when we double n, we only get one more operation, instead of n number of operations like in bubble or insertion sort.
Instructor: [00:00] Merge sort is a recursive sorting algorithm. If you don't understand recursion, I recommend finding a resource to learn it. In brief, recursion is the act of a function calling itself. Thus, merge sort is accomplished by the algorithm calling itself to provide a solution.
[00:17] Merge sort divides the given array into two halves, a left half and a right half. We call merge sort on these sub-arrays. We continue to split our sub-arrays until we get arrays whose length is less than two. We then begin to stitch our small arrays back together, sorting them on the way up.
[00:36] This is an efficient algorithm because we start by sorting very small arrays. By the time we reach our larger ones, they are already mostly sorted, saving us the need for expensive loops. To create our algorithm, we'll actually need two functions, our merge sort function and a merge function that does the combining and sorting of our sub-arrays.
[00:58] Merge sort receives an array as an argument. Since this function will be called recursively, we want to start with our base case scenario, that is the scenario in which we want to return right away rather than call it recursively. In our case, if the array we received has a length that's less than two, we need to return that array.
[01:18] There's no further splitting that we need to do. Otherwise, if the array is longer than two, we need to divide it into left and right halves. I'm going to do that by finding the middle using math.flor and dividing the array length by two. This will give me an index I can use to divide the array into two sub-arrays.
[01:38] We'll create our left array by using slice from zero to middle. We'll create our right array by using slice starting at the middle. Now that we have our left and right sub-arrays, as I explained before, what we're going to do is return a merged function that's calling merge sort on the left half and the right half.
[01:59] Now that we have our merge sort function created, we need to create the merging function that will actually take our two sub-arrays and sort them out and stitch them back together. Our merge function needs an array that we can store our sorted items into. We'll create that first.
[02:19] Now what we want to do is compare the first items in both the left and the right arrays. If the left item is less, we push that into our sorted array. If the right item is less, we push that into our sorted array. Since we're comparing these items and stashing them into the sorted array, we actually want to remove them from the left and the right arrays.
[02:41] In this case since we're pulling from the beginning, we'll use the shift method. Now as we're doing this, we're changing the length of our arrays. We only want to compare them when we know that we have values in both arrays. We should do this during a while loop that makes sure that we have length in both arrays.
[02:59] Now we need to consider a situation in which we've depleted the left or the right array but there are still items in the remaining array. What we want to do is we want to stitch together our sorted results and then place the remaining items in either the left or the right into a new array and return that.
[03:18] I'm going to call this array results, and we'll use the spread operator to spread our sorted array then the left array and the right array. If the left or the right array is empty, it'll spread nothing. Then if the other one still has items, it'll spread the remaining items into it. To add some interest to this as we watch the algorithm take place, I want to actually log out the results for each merge.
[03:42] Now that we have our merge sort function completed, let's create an array of unsorted numbers and call merge sort on them. Let's try logging out the results of our merge sort. You can see one stack merged 5 and 10, the next, 7 and 8, the next, put 4, 7, and 8 in the right places, then 4, 5, 7, 8, and 10 as it merged those all together.
[04:04] Then, we got to the right half of our array. We had one and two got sorted, which were two and one, six and nine got sorted, then three, six, nine. Then, one, two, three, six, nine. Then we combine our two lengths of 5 together to end up with our sorted array, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10.