Blog

JavaScript Insertion Sort Algorithm
Posted on July 14, 2015 in Algorithms, JavaScript by Matt Jennings

See this Wikipedia entry for the insertion sort algorithm. This animated GIF from that entry explains more details about how the algorithm should work:

function insertionSort(arr) {
  for(var i = 0; i < arr.length; i++) {
    
    // Set "temp" variable to "arr[i]"
    var temp = arr[i];
    
    // Execute for loop when
    // 1. "j" is assigned to "i"
    // 2. "j" is greater than zero && "temp" (assigned to "arr[i]") is
    //    less than "arr[j - 1]" (AKA "arr[i - 1]")
    // 3. Decrement "j" by 1 until "j" is greater than zero
    for(var j = i; j > 0 && temp < arr[j - 1]; j--) {
      
      // If conditions in the form loop are true assign
      // "arr[j]" (AKA "arr[i]") to the previous element
      // "arr[j - 1]" (AKA "arr[i - 1]")
      arr[j] = arr[j - 1];
    }
    
    // When the for loop completed break out of it and
    // swap the variables "arr[j]" (AKA "arr[i]") AND 
    // "arr[j - 1]" (AKA "arr[i - 1]") when
    // "arr[j] < arr[j - 1]" (AKA "arr[i] < arr[i - 1]")
    arr[j] = temp;
  }
  
  return arr;
}

var x = [5, 1, 19, 17, -8];

// Code below outputs:
// [-8, 1, 5, 17, 19]
console.log(insertionSort(x));