[MUSIC PLAYING] 

DOUG LLOYD: So insertion sort is another algorithm we can use to sort an array. The idea behind this algorithm is to build your sorted array in place, shifting elements out of the way as you go, to make room. This is slightly different from selection sort or bubble sort, for example, where we're adjusting the locations, where we're making swaps. 

In this case what we're actually doing is sliding elements over, out of the way. How does this algorithm work in pseudocode? Well let's just arbitrarily say that the first element of the array is sorted. We're building it in place. 

We're gonna go one element at a time and build it, and so the first thing we see is a one element array. And by definition, a one element array is sorted. 

Then we'll repeat this process until-- we'll repeat the following process until all of the elements are sorted. Look at the next unsorted element and insert it into the sorted portion, by shifting the required number of elements out of the way. Hopefully this visualization will help you see exactly what's going on with insertion sort. 

So again, here's our entire unsorted array, all of the elements indicated in red. And let's follow the steps of our pseudocode. The first thing we do, is we call the first element of the array, sorted. So we're just gonna say five, you're now sorted. 

Then we look at the next unsorted element of the array and we want to insert that into the sorted portion, by shifting elements over. So two is the next unsorted element of the array. Clearly it belongs before the five, so what we're gonna do is sort of hold two aside for a second, shift five over, and then insert two before five, where to should go. And now we can say that two is sorted. 

So as you can see, we've only so far looked at two elements of the array. We haven't looked at the rest at all, but we've got those two elements sorted by way of the shifting mechanism. 

So we repeat the process again. Look at the next unsorted element, that's one. Let's hold that aside for a second, shift everything over, and put one where it should go. 

Again, still, we've only ever looked at one, two, and five. We don't know what else is coming, but we've sorted those three elements. 

Next unsorted element is three, so we'll set it aside. We'll shift over what we need to which, this time is not everything as in the previous two cases, it's just the five. And then we'll stick three in, between the two and the five. 

Six is the next unsorted element to the array. And in fact six is greater than five, so we don't even need to do any swapping. We can just tack six right on to the end of the sorted portion. 

Lastly, four is the last unsorted element. So we'll set it aside, shift over the elements we need to shift over, and then put four where it belongs. And now look, we've sort of all the elements. Notice with insertion sort, we didn't have to go back and forth across the array. We only went across the array one time, and we shifted things that we'd already encountered, in order to make room for the new elements. 

So what's the worst case scenario with insertion sort? In the worst case, the array is in reverse order. You have to shift each of the n elements up to n positions, every single time we make an insertion. That's a lot of shifting. 

In the best case, the array is perfectly sorted. And sort of like what happened with five and six in the example, where we could just tack it on without having to do any shifting, we'd essentially do that. 

If you imagine that our array was one through six, we'd start off by declaring one is sorted. Two comes after one so we can just say, OK, well one and two are sorted. Three comes after two so, OK, one and two and three are sorted. 

We're not making any swaps, we're just moving this arbitrary line between sorted and unsorted as we go. As effectively as we did in the example, turning elements blue, as we proceed. So what's the worst case runtime, then? Remember, if we have to shift each of the n elements possibly n positions, hopefully that gives you an idea that the worst case runtime is Big O of n squared. 

If the array is perfectly sorted, all we have to do is look at every single element once, and then we're done. So in the best case, it's omega of n. 

I'm Doug Lloyd. This is CS50.