DOUG LLOYD: So in this video, we're going

to take a look at insertion sort, which is another algorithm that you

can use to sort an array.

And in this example, we're going to use an array of integers.

An algorithm, recall, is a step by step set

of instructions for completing a task.

The idea with insertion sort is as follows,

we're going to build the sorted array in place, shifting elements that

were previously considered sorted, if we need to,

in order to fit those elements in the right position

in the sorted portion of the array.

This is fundamentally different than how we've done things

with selection sort or bubble sort.

Recall with those algorithms what we do is,

we usually end up just sorting one element.

We have to go through the entire array to put

one element in the correct position.

For bubble sort, it's usually the largest element that's available.

For selection sort, it's usually the smallest element.

But we're only getting one at a time.

We're not making-- you know, we have to go through this array multiple times.

With insertion sort, we only are going to move forward through the array once.

We might have to look back at things we've already sorted to sort of shift

them around to make room.

But we only have to make one forward pass of the entire array.

So that's sort of a fundamental difference.

And the way we do this is we get started, we just

say the first thing we see is sorted.

It's the only thing we've seen so far.

So it might as well be sorted.

Then we just do the following for every element that remains.

We look at that element and we maybe shift things

that we previously considered sorted, just

to make room for it, until we get through every single element.

This will probably make a little bit more sense when you see it visually.

So let's illustrate that now with this array.

In this array, what I want to do is everything that's red is unsorted,

everything that's blue is sorted.

So keep that in mind as we go through this example.

So recall that the first thing we do is we

declare the first element of the array is sorted.

So that's five.

We just see it.

We're like, got it.

This one is sorted.

So we have the sorted portion in blue.

And we this five element unsorted portion in red.

Now we're going to repeat the following process

until everything else is sorted.

We look at the next unsorted element and we maybe

shift things around in the blue section in order

to put that element in the correct sorted position.

So the first element that we see is two.

We take a look, we see is there anything we need

to do to put two in the right spot.

The answer is yes.

We need to shift five over in order to put two in front of it.

So we slide five over.

And then we put two where five basically was in memory.

And now two, five is sorted and the red portion is unsorted.

Let's repeat this process again.

The next thing we see is a one.

We take a look at the blue portion.

What do we have to move?

Well here, again, we have to move everything,

because one comes before both two and five.

So both of them slide over.

And that leaves one vacancy to put the one.

The next thing we see is three.

What do we have to move this time in order to get everything into position?

Well, it's not everything this time.

We just have to move the five over.

So we move the five to where the three was.

And then we put the three where the five just vacated.

The next element that we see is 6.

And this is sort of a special case of insertion sort, where

it's larger than everything in the sorted portion, which

is great because then we don't have to move anything at all.

We just say, all right, well, six is in the right spot.

We can just declare six to be sorted.

And then the final element we have here is four.

So we take a look at that.

We look back at the blue portion, the sorted portion of the array.

We figure out what we need to slide over.

It's just the five and the six.

They slide over which makes room for the four.

And now we have sorted our entire six element array using the insertion sort

algorithm.

Now again, this feels very different than anything we've seen before.

But unfortunately it's still n squared algorithm.

So for example, imagine if the array is in reverse order.

So it's six, five, four, three, two, one.

In that case, we have to shift each of the elements n positions every time we

want to make an insertion.

So we see this six, five, four, three, two, one array.

The six is good.

Then we see the five.

We have to shift the six over.

Then we see the four.

We have to shift of six and the five over.

Then we see the three.

We have to shift the six and the five and the four.

So we just keep getting worse.

We have to keep making all these shifts.

And each one of those costs us.

So even though this looks and feels very different

than a bubble sort or a selection sort, this is still n squared, unfortunately.

In the best case scenario though, the array is perfectly sorted.

And this is sort of that example we saw a second ago with the five and the six,

where we just said, oh, well that's kind of convenient.

The six is greater than everything in the sorted portion,

so we just kind of moved the line over.

We just changed it from red to blue without changing anything.

In the best case scenario, we just do that for every element-- one, two,

three, four.

We just keep changing them red to blue, no shifts.

And so if we think about this in asymptotic notation, that

means that this algorithm is a big O of n squared, but it's still omega of n.

I'm Doug Lloyd.

This is CS50.