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.

Main content

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 n1 into the sorted subarray in indices 0 through n2.
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?

  • piceratops seedling style avatar for user Steve
    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.
    (3 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      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
      (17 votes)
  • primosaur seed style avatar for user debaratibanerjee80
    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??
    (3 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      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
      (8 votes)
  • duskpin ultimate style avatar for user LearnCat
    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]);
    (3 votes)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      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.
      (3 votes)
  • blobby green style avatar for user Cris
    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]);
    (2 votes)
    Default Khan Academy avatar avatar for user
  • leaf blue style avatar for user Miki  Munna
    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?
    (2 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user vlyeduru
    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.
    (2 votes)
    Default Khan Academy avatar avatar for user
  • leafers tree style avatar for user Fakhrul I. Maruf
    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)
    Default Khan Academy avatar avatar for user
    • male robot hal style avatar for user Cameron
      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
      (3 votes)
  • aqualine ultimate style avatar for user Dave Kes
    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.
    (2 votes)
    Default Khan Academy avatar avatar for user
  • blobby green style avatar for user Lopez, Damian
    var insertionSort = function(array) {
    for(var i = 0; i < array.length-1; i++) {
    insert(array, i , array[i+1])
    (2 votes)
    Default Khan Academy avatar avatar for user
  • leaf green style avatar for user Gabriel M
    For the insertion sort function, when I use i = 0, i, and i+1, I get the function is taking to long error.
    But when I use i = 1, i-1, and i, I don't get any error.

    Though when I println the numbers, everything is the same in both cases. Why is this happening?
    (2 votes)
    Default Khan Academy avatar avatar for user