[MUSIC] So sorting is a very important topic and as I promised we're going to do more with it. So in our first case we saw a very simple sort, bubble sort. It's not very efficient, works fine for small cases because computers are very fast. Now, let's look at something that's quite efficient and it's going to be called merge sort and the idea behind it is a very important idea for all of computer science and algorithms and programming so the divide-and-conquer strategy. In merge sort the principal idea is that you have two existing sorted piles? And you want to turn them into a combined sorted pile. So pile A and pile B will be merged into pile C. And let's look at the specific case and it will show in a way the algorithm for the very general case. So if pile A had 3, 5, and 7 in it and pile B had 1, 2 and 4 in it. Don't forget the piles are already going to be merged and then they're going to be merged into bigger piles that are already sorted. So you look at the two smallest elements, you know that the smallest element in the resulting piles be has to be chosen between one of those two. So if one e at any time for the next smallest candidate you have only two choices the bottom of the pile. So look at the bottom one and three, well one's your choice, so we move one in now your choice is two and three so you move two in, now your choice is three and four. So you move three in, now your choice is four and five so you move four in and now you're not letting you don't have anything in this pile. So you have a cleanup phase. The rest of this pile is already in order. So you just move it directly five and seven and that's the general idea. So the heart of merge sort is take small piles, merge them, take bigger piles, merge them. Keep going until everything is merged into one sorted order turns out and I won't do that rigorously again. I told you about Knuth volume three sorting and searching and you can look at it and other books or as well and something like a Wikipedia page. You can show that such a procedure is going to be order n log n where n is the number of elements to be sorted. Now, let's look at the heart of the algorithm. Here we are. in this algorithm we have as our merge pile A, pile B and the result pile C. Pile A has size n and pile B has size n so we can generalize it though it turns out, for our purposes, the ideal is to have the piles be equal or indeed be roughly a power of two. That would be your most efficient. But we have three indexes and these are to keep track of where we are in the three piles, K will be the result pile. I will be the pile A, J will be the index in the pile B. We can do this all with a while loop. While I less than M the size of pile A and J is less than n the size of pile b, this is the logical operator and we have a simple if A less than B then shove A in to C or to increment both of these indexes which means move to the next element in each of those piles else place into the C pile the B element. You either place an a element or a b element. If it's an a element you advance the a index, if it's a b element you advance the b index. And in either case, you're going to advance the c index one. Ultimately you're going to finish. And there's going to be some cleanup you might not have gotten to the end of both simultaneously. So you look to see if you're at the end of pile a. If you're not at the end of pile a means it has some elements remaining and you just can shove them in turn. That's your while statement enter your merge pile c. Similarly if J is less than n then you can merge the rest of the b pile into c just as we did in our simple example. So that's your basic merge algorithm and that will be at the heart of a merge sort that will continually call starting with piles of two appropriate sizes, merge them. And you'll finish with having the whole list sorted. Okay. What we're going to do next is actually show the whole routine encode. So we'll just do that in code. But this is the heart of the thing to remember and if you're not trying to get to a sophisticated computer science understanding just go with bubble sort and just know that there are other sorts available to you that are more efficient namely order n log and sorts where bubble sort is order n squared so it's not so efficient. [MUSIC]
