If you're seeing this message, it means we're having trouble loading external resources on our website.

If you're behind a web filter, please make sure that the domains *.kastatic.org and *.kasandbox.org are unblocked.

Insertion sort

# Insertion sort pseudocode

Now that you know how to insert a value into a sorted subarray, you can implement insertion sort:
1. Call insert to insert the element that starts at index 1 into the sorted subarray in index 0.
2. Call insert to insert the element that starts at index 2 into the sorted subarray in indices 0 through 1.
3. Call insert to insert the element that starts at index 3 into the sorted subarray in indices 0 through 2.
4. Finally, call insert to insert the element that starts at index n, minus, 1 into the sorted subarray in indices 0 through n, minus, 2.
As a reminder, here's the visualization that steps through the algorithm on a deck of cards:

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?

• Why do you we have to use "var someFunc = function() {}" rather than "function someFunc() {}" ? The differences between the two are minor and I prefer the latter syntax when possible.
• The code inside the code window is working within an environment.
-variables and object which appear to be global within the environment aren't really global in scope, they are just at the scope level that the environment is at
- I suspect that, you can't use function foo(){} because this would make the function truly global
i.e. it would be at the level of the window object, which could cause all kinds of problems
- I suspect, the same rationale applies to why variables must be declared using var instead of them automatically being created as globals

So, I believe that the syntax is restricted, because you're stuck in the Matrix, and allowing you to use the restricted syntax would cause the illusion to be shattered.

Hope this makes sense
• in the inset function 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;
};

can someone explain to me array[j + 1] = value; this line?
I know array[j + 1] = array[j]; this is sliding all bigger element than the value to its right but should not the small value be inserted at array[j] position? why array[j+1] position??
• if you exited the loop you have just failed the check for j >= 0 && array[j] > value.

There are two cases where this would happen:
1) j is -1, (to the left of the array), in which case value is the smallest element, which you want to be inserted at index 0.
Note that: j + 1 = -1 + 1 = 0

2) j is the index of the largest element that is smaller than value. In which case you want to insert value immediately after it i.e. j+1
• I can't understand what happen with the array of learn?
I think it should print
Array after sorting:   [10, 23, 25, 32]

but it not?
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 i = 1; i < array.length; i++) {        insert(array, i-1, this.array[i]);    }};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]);var learn = [10, 23, 32, 25];insertionSort(learn);//println(learn);println("Array after sorting:  " + learn);Program.assertEqual(learn, [10, 23, 25, 32]);
• You shouldn't need to use this
When you use this.array it is referring to the var array declared outside of the function, instead of the local var array that was passed in as a parameter the function. Remove the this and things should work better.
• what is the wrong with below code ??

[Edited to include only relevant code]
var array = [78, 34, 99, 88, 29, 7, 42];insertionSort(array);println("Array after sorting:  " + array);Program.assertEqual(array, [7, 29, 34, 42, 78, 88, 99]);
(1 vote)
• The code is fine, but you have changed the original array and assert, which is confusing the grader

The original array is: var array = [22, 11, 99, 88, 9, 7, 42];
The original assert is: Program.assertEqual(array, [7, 9, 11, 22, 42, 88, 99]);

Change those two lines back to the original and it should work ok
• I have written this code and the error message is showing that a function is taking to log to run and it is pointing to the insert function which is pre-written

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 i=1; i<array.length ; i++)
{
insert(array,i,array[i]); }
};

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]);
(1 vote)
• This might be because in the loop, the condition is i < array.length. However, while running the code, array length increases because of the insert function. So, the loop cannot end.
• Isn't this more logical :

var insertionSort = function(array) {
for(var i = 0; i < array.length-1; i++) {
insert(array, i , array[i+1]);
}
};

than this :

var insertionSort = function(array) {
for(var i = 1; i < array.length; i++) {
insert(array, i-1 , array[i]);
}
};

why start from i = 1, instead of i = 0?
(1 vote)
• The 1st element at index 0 is already sorted, so starting at 1 skips it.
(1 vote)
• Write an algorithm for a function named finder that recursively goes through a list and returns
the index of the first occurrence of an item of interest. The function takes three parameters: 1. The first
position in the list (or 0) 2. The list we want to iterate over 3. The item we want to find.
If the item is not there in the list and we have iterated over the whole list, then the function should return
0.
(1 vote)
• This sentence doesn't make sense to me. Can someone reword this statement in another way?
Call insert to insert the element that starts at index 1 into the sorted subarray in index 0.
(1 vote)
• Hi, guys!

I have completed the challenges for this section (implement insert and insertion sort) and realized on the implement insert that the array is slightly messed with. It removes the value immediately to the right of the rightValue. How would I change this so that it doesn't do that?

Also, is there a reason behind having the for loop in the insert function reverse and the one in the insertion sort go forwards? I tried (a little) to change the second one to a reverse loop, but couldn't get the code.

Thanks for the help!
(1 vote)
NOTE: Spoiler for the next challenge.

When I input these liens of code
[Edited to Remove Code]

The grader would not accept what I was doing, because the program was taking too long, and then there was a syntax error. BUT, when I made a different function, copied the old function entirely, pasted it into the new function, and deleted the old function, the grader said that there was an error in the code. After I was working for a while, trying to figure out what was wrong, I decided to leave the page and come to this one for help on what to do. (Thanks Bob Johnson by the way.)

When I looked at what others had done, and had an explanation for it, I decided to look back at my code, and see what was different. So I clicked on the exercise, and reloaded it. This time, the grader had said that it was complete, even though I did nothing to it.

My question is, are there fatal inconsistencies with the grader, or is it just a problem with the application itself loading the program?

Thanks!
(1 vote)
• Possible causes of the issue:
-You inadvertently introduced a small change in your code that corrected it (believe it or not, in these types of cases, this is usually what happened)
-The syntax error and grader application were lagging, and need some time to catch up to your code (from time to time this happens)
-The syntax error and grader application missed the signal that you changed your code, and needed to get a signal to check the code again (adding a blank line by pressing enter usually wakes the applications up)