As discussed in my last post, I’ve been spending time learning new algorithms, and reminding myself how to use ones that I haven’t used in years.
Here is the evolution of my Merge Sort algorithm:
I did some searching online looking for a high-level discussion of what a merge sort was, and it’s pros and cons. tldr: It trades the usage of more space for better performance than Quick Sort.
Then I found this example by Tim Han.
I scanned through that quickly, and then worked on other stuff for several days. When I came back to take my first shot at writing my merge sort (crazily enough, this isn’t one that I encountered during my year and a half of computer science classes many, many years ago), all I remembered was that you divide the array, and then you return a merge call of those array halves being recursively divided. Oh, and something about there being a single leftover data point that needed tacked onto something else at the end of the merge.
Here is my first compilable attempt:
//Mergesort. Works by splitting array into half until getting arrays of size 1
//Then merges the arrays back together, sorting as they are merged.
const mergeSort = (array) => {
const length = array.length;
if(length == 1) {
return array;
}
const midpoint = Math.floor(length / 2);
let left = array.slice(0,midpoint);
let right = array.slice(midpoint);
return merge(mergeSort(left), mergeSort(right));
}
const merge = (array1, array2) => {
if(!array2.length) {
return array1;
}
let mergedArray = [];
while(array1.length && array2.length) {
if(array1[0] <= array2[0]) {
mergedArray.push(array1.shift());
} else {
mergedArray.push(array2.shift());
}
}
if(!array1.length) {
while(array2.length) {
mergedArray.push(array2.shift());
}
}
if(!array2.length) {
while(array1.length) {
mergedArray.push(array1.shift());
}
}
return mergedArray;
}
const rawArray = [9,1,2,3,4,5,7,88,77,5,5,66,3,8,7,49,59,62,73,24,81,67,32,5,3,2];
let sorted = mergeSort(rawArray);
console.log(sorted);
As a side note, the reason that the version I wrote on paper didn't work was two-fold.
1. I just merged left and right inside of "mergeSort" rather than merging what was returned from calling mergeSort on each of those two array halves.
2. I used a Math.ceil rather than a Math.floor to generate the midpoint, which resulted in an array of length two not being properly split.
While writing my initial algorithm, the merge is the part that gave me pause, primarily, because I couldn't see how we could consistently guarantee that once we were done with the while loop that there would just be one item in one of the arrays. I could envision a scenario (for instance in an already-sorted array), where array1 gets emptied before any items are taken from array2
After a few minutes, I just went with my gut, and created something that would deal with emptying an unknown number of items out of whichever of the arrays still had items in it.
Once I'd confirmed that my code was compiling and properly sorting the array, I went back to Tim Han's algorithm and compared it to what I'd come up with.
The biggest thing that stuck out to me was the fact that he was using pointers rather than shifting items off of the two arrays passed into the merge function.
The more experienced of you are already nodding your heads, and don't need me to tell you that his approach is superior, but in my defense, I'm used to thinking in terms of JavaScript arrays, which are different than how most languages define an array.
In Java, an array is created with a pre-determined size and you can't grow or shrink that array after it is created. Instead, you have to create a new array of the desired size and copy the desired items from the first array into the new array.
The fact that Java arrays are all a single contiguous block of memory likely makes them faster than JavaScript arrays, which as I understand it are just objects that can be added to and removed from without creating a new object and destroying the old object.
Still, even running this in JavaScript, there isn't any reason that we have to shorten array1 and array2 while growing the mergedArray--unless maybe memory was becoming a constraint and we needed to free up the space being occupied by array1 and array2 simultaneously to growing the mergedArray.
Still, though, that seems unlikely. Generally, you'd just run things on a machine with more memory, or use a streaming type approach to the algorithm.
The next thing that I noticed was that I didn't need my if(!array2.length) statement. Ultimately, if array2 (or array1 for that matter) were empty, it's just going to skip the while loop and tack the other array onto the mergedArray.
Lastly, the use of the concat function rather than a while loop was nice and slick. It's another reminder that I need to spend some time just reading through JavaScript's built-in methods and arrays. I know a bunch of them by memory, but there are still tons of them that I don't use because I don't realize that they are out there.
Here's my updated version:
//Mergesort. Works by splitting array into half until getting arrays of size 1
//Then merges the arrays back together, sorting as they are merged.
const mergeSort = (array) => {
const length = array.length;
if(length == 1) {
return array; //split down as far as we can go. Time to return so we can merge.
}
const midpoint = Math.floor(length / 2);
let left = array.slice(0,midpoint);
let right = array.slice(midpoint);
return merge(mergeSort(left), mergeSort(right)); //split left and right again and the merge what comes back
}
const merge = (left, right) => { //merge the two arrays together into a sorted array
let mergedArray = [];
let leftIndex = 0;
let rightIndex = 0;
while(leftIndex < left.length && rightIndex < right.length) {
//compare the two and put the smallest into mergedArray until we get to the end of one of them
if(left[leftIndex] <= right[rightIndex]) {
mergedArray.push(left[leftIndex]);
leftIndex++;
} else {
mergedArray.push(right[rightIndex]);
rightIndex++;
}
}
//either left or right will still have values that can be tacked onto the end of
//our sorted array
let leftRemainder = left.slice(leftIndex);
let rightRemainder = right.slice(rightIndex);
return mergedArray.concat(leftRemainder).concat(rightRemainder);
}
const rawArray = [9,1,2,3,4,5,7,88,77,5,5,66,3,8,7,49,59,62,73,24,81,67,32,5,3,2];
let sorted = mergeSort(rawArray);
console.log(sorted);
Performance wise, my algorithm is the same now as what Tim did (which makes sense given that I read his algorithm several days before sitting down to do my own). I explicitely broke out the leftRemainder and rightRemainder because I think it's easier to follow what's going on that way.
I did confirm that while Tim's algorithm is great, he was wrong about there being just a single item left over after the while loop in the merge function. If you log leftRemainder and rightRemainder out, you'll see that they can be more than 1 item.
A big thanks to Tim for putting such a clear, well-written algorithm out there!