MergeSort

That’s right, another sorting blog! SO the past few sorting examples I discussed in my earlier blogs were fairly novice sorting methods. Do they do the job? Yes. However, they do not always scale well and sometimes only work when your information is already sorted to an extent.

With that said, another type of sorting method is MergeSort. MergeSort is typically faster than Bubble, Insertion, or Selection sort with a time complexity of O(nlogn). On the flip side though, it can be a bit more complex in terms of understanding how it works.

The concept of MergeSort is this:

Break an array of elements down to where there is only 1 element in its own array. THEN build the array back up with the same elements while sorting them at the same time.

I like to remember that odd phrase “You first need to break someone down first so that they can be built back up stronger. Although it may not be the best advice to give to a person, it is the main concept of MergeSort. here is an example of what it would look like if you work with an array:

[8,3,5,4,7,6,1,2]

You would split it up to [8,3,5,4] and [7,6,1,2]

Then to [8,3] and [5,4] and [7,6] and [1,2]

And finally to [8] and [3] and [5] and [4] and [7] and [6] and [1] and [2]

Then merge them back sorted

So [3,8] and [4,5] and [6,7] and [1,2]

Then [3,4,5,8] and [1,2,6,7]

Finally [1,2,3,4,5,6,7,8]

To do this though, you will need to first spilt things up, and then merge them. SO this will require two functions. Lets focus on the merging function first

Then, after you have a merging function, you will want to split them up. The best way to split would be with splice. But Thomas, how do you do it for each item in an array? Well you would want to look at my Recursion blog, because we will be using that!

//Keep going recursively until our base case is arr.length<=1.Once all are single, merge those arrays with the other sorted arrays until you are back to the full length. Then return sorted merged array