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.

## Computer science

### Course: Computer science>Unit 1

Lesson 5: 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]); • 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]); • 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? • 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. • 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) • 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.   