Main content

## Computer science

# Insertion sort

There are many different ways to sort. As selection sort runs, the subarray at the beginning of the array is sorted, but the subarray at the end is not. Selection sort scans the unsorted subarray for the next element to include in the sorted subarray.

Here's another way to think about sorting. Imagine that you are playing a card game. You're holding the cards in your hand, and these cards are sorted. The dealer hands you exactly one new card. You have to put it into the correct place so that the cards you're holding are still sorted. In selection sort, each element that you add to the sorted subarray is no smaller than the elements already in the sorted subarray. But in our card example, the new card could be smaller than some of the cards you're already holding, and so you go down the line, comparing the new card against each card in your hand, until you find the place to put it. You insert the new card in the right place, and once again, your hand holds fully sorted cards. Then the dealer gives you another card, and you repeat the same procedure. Then another card, and another card, and so on, until the dealer stops giving you cards.

This is the idea behind

**insertion sort**. Loop over positions in the array, starting with index 1. Each new position is like the new card handed to you by the dealer, and you need to insert it into the correct place in the sorted subarray to the left of that position. Here's a visualization that steps through that:In terms of arrays, imagine that the subarray from index 0 through index 5 is already sorted, and we want to insert the element currently in index 6 into this sorted subarray, so that the subarray from index 0 through index 6 is sorted. Here's how we start:

And here's what the subarray should look like when we're done:

To insert the element in position 6 into the subarray to its left, we repeatedly compare it with elements to its left, going right to left. Let's call the element in position 6 the

**key**. Each time we find that the key is less than an element to its left, we slide that element one position to the right, since we know that the key will have to go to that element's left. We'll need to do two things to make this idea work: we need to have a**slide**operation that slides an element one position to the right, and we need to save the value of the key in a separate place (so that it doesn't get overridden by the element to its immediate left). In our example, let's pull the element at index 6 into a variable called`key`

:Now, we compare

`key`

with the element at position 5. We find that `key`

(5) is less than the element at position 5 (13), and so we slide this element over to position 6:Notice that the slide operation just copies the element one position to the right. Next, we compare

`key`

with the element at position 4. We find that `key`

(5) is less than the element at position 4 (10), and we slide this element over:Next, we compare

`key`

with the element at position 3, and we slide this element over:The same happens with the element at position 2:

Now we come to the element at position 1, which has the value 3. This element is less than

`key`

, and so we do *not*slide it over. Instead, we drop`key`

into the position immediately to the right of this element (that is, into position 2), whose element was most recently slid to the right. The result is that the subarray from index 0 through index 6 has become sorted:Insertion sort repeatedly inserts an element in the sorted subarray to its left. Initially, we can say that the subarray containing only index 0 is sorted, since it contains only one element, and how can a single element

*not*be sorted with respect to itself? It must be sorted. Let's work through an example. Here's our initial array:Because the subarray containing just index 0 is our initial sorted subarray, the first key is in index 1. (We'll show the sorted subarray in red, the key in yellow, and the part of the array that we have yet to deal with in blue.) We insert the key into the sorted subarray to its left:

Now the sorted subarray runs from index 0 through index 1, and the new key is in index 2. We insert it into the sorted subarray to its left:

We keep going, considering each array element in turn as the key, and inserting it into the sorted subarray to its left:

Once we've inserted that rightmost element in the array, we have sorted the entire array:

A couple of situations that came up in our example bear a little more scrutiny: when the key being inserted is less than all elements to its left (as when we inserted keys 2 and 3), and when it's greater than or equal to all elements to its left (as when we inserted key 13). In the former case, every element in the subarray to the left of the key slides one position to the right, and we have to stop once we've run off the left end of the array. In the latter case, the first time we compare the key with an element to its left, we find that the key is already in its correct position relative to all elements to its left; no elements slide over and the key drops back into the position in which it started.

### Inserting a value into a sorted subarray

The main step in insertion sort is making space in an array to put the current value, which is stored in the variable

`key`

. As we saw above, we go through the subarray to the left of `key`

's initial position, right to left, sliding each element that is greater than `key`

one position to the right. Once we find an element that is less than `key`

, or equal to `key`

, we stop sliding and copy `key`

into the vacated position just to the right of this element. (Of course, the position is not truly vacated, but its element was slid over to the right.) This diagram shows the idea:This content is a collaboration of Dartmouth Computer Science professors Thomas Cormen and Devin Balkcom, plus the Khan Academy computing curriculum team. The content is licensed CC-BY-NC-SA.

## Want to join the conversation?

- Hi, im getitng this error message:

"

Instead of relying on the array's undefined values at negative indices, can you explicitly check that you're at the beginning of the array?

"

And don't really understand, what I suppose to change?(24 votes)- What it is complaining about is:

if you try to read array[i] and you don't check the value of i then i might be a negative value

e.g. if i=-1 it will try to read array[-1]

This is bad, because array[-1] is one element before the array (it is not in the array) i.e. it is trying to read something that doesn't exist

Different programming languages will handle this differently:

- JavaScript will return "undefined"

- Java will throw an error

- C or C++ will let you read the memory before the array, which will cause very unpredictable results.

No matter what language it is, it's a bad idea to attempt to read from or write to array indexes that are before or after your arrays elements ( < 0 or >= array.length ). It means that have a made a mistake by attempting to read from or write to something that shouldn't exist.

Hope this makes sense(35 votes)

- I'm having a brain wobble and I can't stop the index variable from becoming "-1"
**and**still insert the target value in the correct place. For example :`var i;`

for(i = rightIndex ; i > 0 && array[i] > value; i--) {

println(i);

array[i + 1] = array[i];

}

array[i] = value;

with`insert(array, 4, 2)`

using the example (`[3, 5, 7, 11, 13, 2, 9, 6];`

) produces`2,5,5,7,11,13,9,6`

but if I remove the`i > 0`

condition then it sorts to`3,3,5,7,11,13,9,6`

which I can fix with assigning the final value via`array[i + 1] = value`

but then I get the feedback about relying on undefined values.(13 votes)- For the first set of the below questions ignore
`i>0`

completely.

To understand what you should have after the for loop try asking yourself these questions:

- What is the value of`i`

**after**the program exited the for loop compared to the values of`i+1`

and`i`

in the statement:`array[i+1] = array[i]`

on the last iteration of the for loop ?

Remember that on the last iteration of the for loop the program will check the condition (which passes), execute the contents of the for loop, decrement the counter, then check the condition (which fails).

- After the program has exited the for loop, what must be true about the value of`array[i]`

compared to`value`

?

- Based on the answers to the above two questions, where should value be inserted ?

Now, with regards to`i>0`

try asking yourself these questions:

- What is the range of valid array indexes for array ?

- Does the condition in my for loop make sure that invalid array indexes aren't used ?

- Does the condition in my for loop still allow the use of all valid array indexes that might be needed ?

Good Luck(18 votes)

- the first step for "Challenge:implement insert" as follow, i have try several times to find the answer, but expression "array [temp+1] = value;" out of loop i don't understand , why not"array [temp] = value;" ? the final temp value should be "Zero"while temp variable stop looping at Value "Zero". then temp =0 ==> array[temp"0"] = value.

I couldn't find the reason, Could someone help me out? thanks a lots

[Edited to only show relevant code]`var insert = function(array, rightIndex, value) {`

...

for (var temp = ...; temp>=0 && ...;temp--){

...

}

array [temp+1] = ...;

};(6 votes)- Here's how a for loop is executed:

STEP 1: initialize values as per initialization section

STEP 2: check loop condition, if false EXIT

STEP 3: exit contents inside loop

STEP 4: increment/decrement counter as per increment section of for loop (aka afterthought)

STEP 5: Go to STEP 2

So if I have`for(var i=10; i >=0; i--){`

//do something

}

println(i);

the print statement will print -1

Why ?

Let's look at when i = 0.

STEP 2) It checks the loop condition which passes

STEP 3) It executes the loop contents

STEP 4) It decrements i, which is now i= -1

STEP 5) goes to STEP 2)

STEP 2) It checks the loop condition which now fails, so the loop is exited.

Then the print statement prints i, which is -1

The alternate version:

The condition tells you what value i must have while the loop is still running

The counter must have been incremented/decremented one more time to fail that condition if it has exited the loop.

Hope this makes sense(11 votes)

- Hello ! I had an idea while reading this article, and was wondering if someone more savvy than myself could answer. Sometimes it takes a lot of time to go through the whole array (like when you pick a really small number and need to put it at very beginning), but surely we could pick if we go through the subarray from the right or if we go from the left, at each iteration, to gain time ?

Here's some pseudo-code to explain what I mean. Say the ordered array is 0 to 9, and we're at step 6 with [2,3,5,7,9,--4,1,0,8,6] with the elements on the left sorted and the elements on the right unsorted.

Let's define the elements 2 and 9, the first and last of the ordered subarray as being "min" and "max" respectively.

We're going to pick the halfway point of the ordered subarray and figure out on which side our new insertion would be.

If (nextItemToSort (here = 4) <= (min+max)/2), then start from the left (you'll have at most halfway to go), else go from the right (once again, at most halfway to go).

Would such a scheme help to win time and computation power (the asymptotic notation stuff) ? Or is it too computation hungry ? It seems to be an effective system, especially for larger arrays, but I don't know how to prove it. Or is there simply an even better way to sort that makes this idea useless ?

Thank you ! :)(4 votes)- In the regular insertion sort, the worst case cost, is basically the cost of each new inserted element having to traverse through all the previously sorted elements:

1+2+3+4+...n which is ~ 1/2 * n^2

For your proposed sort, if it worked, the worst case cost, is basically the cost of having to traverse half of the previously sorted elements:

1/2 +2/2 + 3/2+... n/2 which is ~1/4 * n^2

It would still run in O(n^2) in the worst case, which is beaten by other sorting algorithms e.g. merge sort is O(n log n).

Now, here's why the proposed algorithm doesn't work that well.

Suppose I want to sort something like this:

0, 1000, 1, 2, 3, 4, 5, 6, ... 500

(In real life, data like this is pretty typical.)

After 0,1000 are sorted, all the rest of the elements will start from the left

Which means they are taking the same time as the insertion sort to get in position, but with the added cost of finding the average of min and max and comparing that average to each element.

Hope this makes sense(4 votes)

- In the next challenge, why do we say array[j + 1] = value; ? Why not array[j] = value; ? I think I'm just having a brain block but it seems like array[j+ 1] would be one index/value too many?(2 votes)
- There are two ways that you will exit the for loop:

- the value of the array[j] is <= value

- j is -1

If the value of array[j] is <= value then value belongs somewhere to the right of array[j]

(in order for array[j] and value to be in the correct order)

array[j+1] is one spot to the right of array[j]

If j= -1 then all of the elements were > value and then value should be inserted at the front of the array, which is array[0]. Since j+1 = -1 + 1 = 0, array[j+1] is where we want to put value

Hope this makes sense(4 votes)

- Phineas Greene asked this question several years ago, and I have the same one. Why not simply use the Array.splice() method instead of creating the insertion function?(3 votes)
- The
`insert`

function here is really a`insertElementIntoSortedPosition`

function.

The insert function has two jobs:

1) finding out**where**to put the new element, so that the array from array[0] to array[rightIndex+1] will be sorted.

2) shifting the elements over to make room for the inserted element

It does both of these jobs at the same time to be efficient.

Array.splice(start, deleteCount, item1) just inserts item1 at start. To replace the insert function you would need to know where`start`

is so that the array[0] to array[rightIndex+1] will be sorted, i.e. you would still need to do the 1st job of the insert function

One should be aware that Array.splice runs in linear time, O(n), as opposed to constant time, O(1), so it can have a large negative impact on running times.

Hope this makes sense(2 votes)

- Wow! This is so cool!(3 votes)
- I wish for these card animation examples, if you can reveal all the cards before I play next step, this would allow us to visualize the next step before playing it and help in way better understanding.(3 votes)
- What is the "slide" function like? Is it like

Key = key;

ThingtoTheLeftofKeyIndex ++;

get new ThingtoTheLeftofKeyIndex

compare again

ThingtoTheLeftofKeyIndex ++;

or something else?(2 votes)- The slide function is basically:

//check if the thing to the left of the key is larger

IF array[keyIndex-1] > keyValue

THEN

//copy the value of that thing to where the keyIndex is

array[keyIndex] = array[keyIndex-1]

//move keyIndex to the left

keyIndex = keyIndex-1

To insert the key in the right position, you repeat this slide until the thing to the left of the key is <= to the value of the key. Lastly you copy the value of the key into the keyIndex.

Note: If you actually code this in the coding challenge it will be a bit different because of how the indexes are defined and due to how for loops adjust their loop counters(2 votes)

- Please Help,Im stuck

the code of step 1 is fine,however i cant pass step 2

(pls tell me what did i do wrong)

var insert = function(array, rightIndex, value) {

for(var j = rightIndex;

j >= 0 && array[j] > value;

j--) {

array[j + 1] = array[j];

}

array[j + 1] = value;

};

var insertionSort = function(array) {

for (var st = 1; st < array.length; st++) {

insert(array, st - 1, array[st]);

}

};

var array = [22, 11, 99, 88, 9, 7, 42];

insertionSort(array);

println("Array after sorting: " + array);

Program.assertEqual(array, [7, 9, 11, 22, 42, 88, 99]);

insert(array, 4, 2);

Program.assertEqual(array,[48, 82, 40, 77, 1, 15, 31]);

insert(array, 5, 9);

Program.assertEqual(array,[93, 90, 49, 56, 29, 40, 42]);

insert(array, 6, 6);

Program.assertEqual(array,[32, 52, 63, 72, 87, 48, 9]);(2 votes)- The tests should be for the
`insertionSort`

function not the`insert`

function(2 votes)