Now, we look at insertion sort which is another elementary method and interestingly has quite different performance, characteristics than selection sort. Let's look at a demo of insertion sort. For insertion sort, what we're going to do is we'll move an index i from left to right as before. But now, in the ith iteration we're going to move a(i) into position among the elements to its left. Let's look at how that works on our example with cards. So now we start by initializing i to first card and we take the idea that everything from i to its left is going to be sorted and everything from the right, we're not going to look at, at all. So, everything to the left of i is in ascending order everything to the right we haven't seen at all yet. So now, when we increment i, well, in this case it's already an order, we don't have anything else to do. In the third case now, when i at the third entry in the array. Now, we start a index j and we move that starting at i to the left and what we need to do is just exchange the five with every element to its left that's greater. So, first we exchange it with the ten. It's still not in place so we exchange it with the seven. Now, we get to the beginning array, of the array and once we've done that or we've hit a smaller element then we have everybody to the left of i in order. [cough] So now we increment i again and we come to the three. Again, we exchange as long as the card immediately to the left is greater. And once we've done that, then we have everything to the left of i in ascending order. Now, in this case, we have the eight and we only have to exchange one and now, it's got the seven to its left and everything is in order. So, we've achieved putting it in order with less work in this case. We don't always have to go all the way back to the beginning. For exchange it with everybody to its left that's greater, until we find a smaller element done in its ascending order. Two has to go all the way back to the begin ning [cough]. But then the very next one, the nine, has to only go back one position. And the sixth has to go about halfway back. [cough] And then, we have the entire array sorted. Again, we can look at insertion sort in terms of invariants. Our pointers still scans from left to right but now, the elements of the left of the pointer, including it, are in order. But the elements to the right have not yet been seen at all. So, we have to look at the code that's going to maintain that invariant as the pointer increments. Move the pointer to the right, it's incremented again. Now, the invariant is broken because the elements the element on the pointer is not in sorted order to put it in sorted order, we have to move from right to left exchanging it with every larger elements to its left. And that's with the code at the bottom does starts j at i and decrements j exchanging j with the elements to its left. A(j) with the element to its left, a(j) - one as long as a(j) is less than a(j) - one or j is bigger than zero. And that immediately gives the, this code for insertion sort which is similar to our code for selection sort and just as simple it gets two nested for loops. Selection sort head to nested four loops a test to comparison and an exchange inside the four loop. And that's a fine implementation of an elementary sorting method. What about the analysis of insertion sort? It's more complicated. Our proposition says that insertions sort to sort randomly ordered array with distinct keys, it'll use about one-fourth N^2 compares and about the same number when one-fourth N^2 exchanges on the average. This is more complicated to prove. It depends on the array being randomly ordered. And again, you can get a feeling for where the propositioning comes from by looking at this N by N trace. Again, the black elements are the ones that we compare and actually, there are also the exchanges. And the red one is the one that's finally put in to place. And you can see t hat for a large array that's randomly ordered, the element that we put into place is going to go about half way back on the average. So, that means about half the elements below the diagonal are going to black on the average cuz N^2 / two below the diagonal, half of that is N^2 / four. The analysis, exact analysis is not much more detailed than that. This is a bigger trace that shows again, about half the elements below the diagonal or involved in the sort. [cough] Let's look at in the animation. Since N^2 / four versus N^2 / two, insertion sort is going to be about twice as fast as selection sort. So, we can do about twice as many items in the trace in the same amount of time. It grabs an element, brings it back into position, every time. So, it's an animation for randomly ordered items. Now insertion sort does depend on the initial order of the data. Let's look at the best case and the worst case which are certainly outliers. If the array happens to be already sorted all insertion sort does is really to validate that each element that's got a smaller element to its left so it does no exchanges and it gets the sorting job done with just N - one compares. On the other hand, if the array is in descending order N is no duplicates, then every element goes all the way back. It makes N^2 / two compares and N^2 / two exchanges. So in the first case is much, much faster than selection sort linear instead of quadratic. In the second case, it's slower than an selection sort cuz it uses about the same number of compares but it uses many more exchanges. So, let's see that in the animation. So, this is when the items come in, in reverse order. Now, every time [cough] it, it gets a new item, that's to exchange it all the way back to the beginning. Same kind of dynamic characteristic is selection sort except for every step, iIt's not just comparing, it's also exchanging which makes it even slower in practice. So, this is the bad case that we wouldn't like to see in th e practical application but there's also a good case that actually we take advantage of in plenty of practical applications. And that has to do with when the array is partially sorted. To talk about this in a quantitative way, we define what's called an inversion. An inversion is just a pair of keys that are out of order in the array. So this array has six inversions, T and R are out of order cuz R should go before T. T and P are out of order and so forth. This array has six inversions. And we define array to be partially sorted if its number of inversions is linear, if it's less than some constant times N. And partially, sorted arrays appear often in practice. For example, if you have a large array with just a few that's sorted except for just a few unsorted elements appended at the end it's going to be [cough] partially sorted. Or another case is if you only have a few entries out of place, the array is going to be partially sorted. These types of things rise often in practical applications and what's interesting about insertion sort is that it runs in linear time for partially sorted arrays. And the proof is the number of comparisons and the number of exchanges is equal to the number of, number of exchanges is equal to the number of inversions and then there's an extra compare for every element except the first. So, let's look at how that looks in the animation. Here's a partially sorted array and you can see that insertion sorts quickly gets the job done. We're going to take advantage of this in a little bit later in this lecture. That's insertion sort, our second elementary sorting