Sunrise in the fog

    Merge Sort

    We've looked at one sort now that is similar to the bubble sort in that they are nested loops that compare numbers to what's directly next to them. But the merge sort is a different beast! To make it, we use recursion - which will help us drastically improve the algorithm.

    Alright, so how does the merge sort work? Well, we'll break the array in half. Then we'll break those two halves in half, and just keep doing that until we have arrays with one item. Then, we'll piece the arrays back together. As we put the different pieces back together, we sort them. Sounds weird at this point - and probably unclear as to how that will actually sort an array. But stay with me. Let's look through the code and then we'll see how it works:

    [gist src=https://gist.github.com/benrgreene/d538e687bd1f0e068ae0d2985b383c48 file=merge.js][/gist]

    So we break the two pieces apart, and recursively sort them so we know they are in order. After those two small pieces of the overall array are sorted we can go over them and pop off the top item of the arrays to put them in an array to return.

    Now the fun part, the complexity of the sort. What's our best case? Well, it's O(n * log(n)). That's absolutley better than the bubble sort or selection sort, which are O(n^2). So, what's the worst case - are we taking a risk using this sort? Turns out, no! The worst case is the same as the best case! By breaking up the array into small arrays and then sorting them, we don't need nested loops. We can perform a single loop over the sub-arrays we are sorting to put them back together - and we only need to perform that loop log(n) times - since we break the arrays in half until they have a length of one, and then they get doubled in size until they're all put back together.

    Now, there is one potential drawback (and why I don't worry about it). Since we are breaking arrays apart and putting them back together, we're creating quite a few arrays - which takes up a bit of memory. This can be a problem on older devices with little memory. The good news is that with modern machines, we've got more than enough memory to create the arrays we need to perform the sort! So unless you're working on a program with lots of threads running asynchronously and chewing through memory, it's not something worth sweating over.

    There it is, the merge sort! Personally, this one is my favorite. Once you get the hang of it, it's real quick and easy to whip up - plus it's got the bonus of being efficient.