# Sorting Algorithms: Insertion Sort using JavaScript

This post covers the essentials of insertion sort using JavaScript. We will use a simple array to demonstrate the concepts of Insertion Sort before getting into code.

# Concept:

In insertion sort, we divide the initial unsorted array into two parts; sorted part and unsorted part. Initially the sorted part just has one element (Array of only 1 element is a sorted array). We then pick up element one by one from unsorted part; insert into the sorted part at the correct position and expand sorted part one element at a time.

Let’s see this using illustration below:

#### Step 1: Initial Array

#### Step 2:

Number 5 is in sorted part of the array. We need to pick up the first number in unsorted part, i.e 3, and insert it into the sorted part at correct position. We make a copy of number 3 and compare this copy with the numbers in the sorted part starting at the last element in the sorted part, in this case, 5.

#### Step 3:

Since 5 > 3, we expand the sorted part by replacing number 3 in the unsorted part by 5. Next, we insert the number 3 (using the copy we stored earlier) at the previous position of 5. Now, the sorted part has expanded to 2 elements while unsorted part is reduced to 3 elements.

#### Step 4:

We pick the next number in the unsorted part, number 1. Again, we make a copy of this number and compare it with numbers in sorted part one by one.

#### Step 5:

Since 5 > 1, we expand the sorted part by replacing number 1 in the unsorted part by 5. We compare the copy of number 1 with the next element in sorted array, 3.

#### Step 6:

Since 3 > 1, we need to shift 3 to next position in the sorted part. We replace the number 5 at the second position with number 3. Since there are no more numbers, we insert copy of number 1 at 1st position.

#### Step 7:

Repeating the same process with number 2, we expand the sorted part and shift numbers 3 and 5:

#### Step 8:

Next, we compare number 2 with number 1. This time, 1 < 2. So, we need to insert the number 2 after number 1. We replace the number 3 at the second position with number 2.

#### Step 9:

Similarly:

## Complexity:

Best Case | Average | Worst Case |

O(n) | O(n²) | O(n²) |

Implementation of Insertion Sort:

```
function insertionSort(unsortedList) {
var len = unsortedList.length;
for (var i = 1; i < len; i++) {
var tmp = unsortedList[i]; //Copy of the current element.
/*Check through the sorted part and compare with the number in tmp. If large, shift the number*/
for (var j = i - 1; j >= 0 && (unsortedList[j] > tmp); j--) {
//Shift the number
unsortedList[j + 1] = unsortedList[j];
}
//Insert the copied number at the correct position
//in sorted part.
unsortedList[j + 1] = tmp;
}
}
var ul = [5, 3, 1, 2, 4];
insertionSort(ul);
console.log(ul);
```

## Practice Exercise:

- Write a program in JavaScript to sort following list in ascending order using Insertion Sort Algorithm.

var nums = [34, 23, 12, 45, 9, 1, 24]; - Sort the list present in Q1 in descending order.
- Sort the following array of Persons in ascending order of ‘age’ using Insertion Sort.

var persons = [

{

"name": "john",

"age": "23"

},

{

"name": "harry",

"age": "21"

},

{

"name": "jack",

"age": "25"

}

];