[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.