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,…