Insertion Sort

Insertion sort is another marvelous sorting algorithm, one that's pretty simple to understand and easy to implement.

The idea is similar to bubble sort. Think of your input array as being made of a sorted left half and an unsorted right half.

One by one, insert an item in its correct place in the sorted half. Insertion is done by comparing the item with successive items before it, and swapping them if needed. To reiterate the steps:

1. Maintain a sorted left sub-array and an unsorted right sub-array.
2. Insert the first key from the unsorted part into its correct place in the sorted half.

The entire pseudo-code that accomplishes the sort is provided here:

1Routine: insertionSort
2Input: Unsorted array X of size n
3
41. totalSorted = 1
52. while totalSorted <= (n-1)
6    {
7        // insert the item at index position totalSorted into top half
8        // by successive comparison with items before it
9        b. i = totalSorted
10        c. while(i > 0 and X[i-1]>X[i])
11        {
12            i. swap(X[i-1], X[i])
13            ii. i--
14        }
15        totalSorted++
16    }

xxxxxxxxxx

function insertionSort(arr) {

  for (let i = 0; i < arr.length; i++) {

    const val = arr[i];

​

    // Arrange the elements prior to the current

    // but greater than it to one position ahead

    let j = i - 1;

    while (j >= 0 && val < arr[j]) {

      arr[j + 1] = arr[j];

      j -= 1;

    }

    arr[j + 1] = val;

  }

  return arr;

}

​

const arr = [41, 19, 23, 3, 4, 19];

console.log(insertionSort(arr));