The merge sort

- [Instructor] Now let's take look at how the merge sort works. The merge sort is known as a divide-and-conquer algorithm. It takes a given set of data and then breaks it down into smaller parts that are easier to work with. It uses recursion to break the data down and then sort the smaller sets of data, gradually working it's way back up to the original dataset. The merge sort has a very good performance profile. It typically operates on it's dataset in logarithmic time, giving it a big O of n log n.

So, that's log linear if you're remembering from our earlier table. So, to understand how the merge sort works, the key is how to merge two sorted arrays together. So let's imagine that we had two arrays that are already sorted and we're going to merge them into one. So, to merge these two while keeping the result sorted, we start with the first elements from the two arrays. In this case, the four is smaller than the 12, so we insert the four, and then we advance the index of the array that we just inserted from to the next element, which is the 23 here, and now we do the comparison again, and now 12 is smaller, so that gets merged in, and then the index advances to the 19.

So 19 is still smaller than 23, so now that gets inserted, and we advance the index over to the 31. And now the 23 is smaller, so that gets merged in, and now we're done with that array. So, we finish up by copying over whatever is left from the other array because it's already sorted, and now we have a single merged array that remains sorted. So this is the key to how the merge sort works. So, how do we get to that state? So let's suppose we had an array of unsorted numbers.

What we do is we successively break that array down until we are left with individual arrays of one element each. So now, we have one-element arrays, all of which are sorted by definition because they only contain one element. Then, we begin merging these arrays back up into each other until we've rebuilt the original array, but this time in sorted form. So, that's pretty much all there is to the merge sort, so let's try implementing that in some real code.