Insertion Sort in JavaScript

  1. Implementation
    1. step 1
    2. step 2
    3. step 3
    4. step 4
    5. step 5
  2. Complexity

Insertion sort is one of sorting algorithms, to better understand it, you could imagine you are playing cards.

Every time you get a new card, compare it with the existing ones, then put it in the right place. While you comparing, we start it from right to left.

The following pictures gives a demonstration of how this sort happended.

Implementation

Let’s start building our insertionSort function.

step 1

1
2
3
4
function insertionSort(arr) {
  var length = arr.length;
  return arr;
}

It’s a best practice to save the array length in a variable.

step 2

1
2
3
4
5
6
7
function insertionSort(arr) {
  var length = arr.length;
  for (var i = 0; i < length; i++) {
    // 
  }
  return arr;
}

We use a for loop to go over the array.

step 3

1
2
3
4
5
6
7
function insertionSort(arr) {
  var length = arr.length;
  for (var i = 0; i < length; i++) {
    let current = arr[i];
  }
  return arr;
}

Save current value in a variable for comparison.

step 4

1
2
3
4
5
6
7
8
9
10
11
function insertionSort(arr) {
  var length = arr.length;
  for (var i = 0; i < length; i++) {
    let current = arr[i];
    let j;
    for (j = i - 1; j >= 0 && arr[j] > current; j--) {
      arr[j + 1] = arr[j];
    }
  }
  return arr;
}

We set up an inner loop in order to put current value in the right place.

step 5

1
2
3
4
5
6
7
8
9
10
11
12
function insertionSort(arr) {
  var length = arr.length;
  for (var i = 0; i < length; i++) {
    let current = arr[i];
    let j;
    for (j = i - 1; j >= 0 && arr[j] > current; j--) {
      arr[j + 1] = arr[j];
    }
    arr[j + 1] = current;
  }
  return arr;
}

Finally assign the the value current to the correct index position.

Complexity

Best case: n
Average: n2
Worst: n2
Memory: 1
Stable: Yes