Insertion sort is a simple sorting algorithm for a small number of elements.

Example:

In Insertion sort, you compare the `key` element with the previous elements. If the previous elements are greater than the `key` element, then you move the previous element to the next position.

Start from index 1 to size of the input array.

[ 8 3 5 1 4 2 ]

Step 1 :

``````      key = 3 //starting from 1st index.

Here `key` will be compared with the previous elements.

In this case, `key` is compared with 8. since 8 > 3, move the element 8
to the next position and insert `key` to the previous position.

Result: [ 3 8 5 1 4 2 ]``````

Step 2 :

``````      key = 5 //2nd index

8 > 5 //move 8 to 2nd index and insert 5 to the 1st index.

Result: [ 3 5 8 1 4 2 ]``````

Step 3 :

``````      key = 1 //3rd index

8 > 1     => [ 3 5 1 8 4 2 ]

5 > 1     => [ 3 1 5 8 4 2 ]

3 > 1     => [ 1 3 5 8 4 2 ]

Result: [ 1 3 5 8 4 2 ]``````

Step 4 :

``````      key = 4 //4th index

8 > 4   => [ 1 3 5 4 8 2 ]

5 > 4   => [ 1 3 4 5 8 2 ]

3 > 4   ≠>  stop

Result: [ 1 3 4 5 8 2 ]``````

Step 5 :

``````      key = 2 //5th index

8 > 2   => [ 1 3 4 5 2 8 ]

5 > 2   => [ 1 3 4 2 5 8 ]

4 > 2   => [ 1 3 2 4 5 8 ]

3 > 2   => [ 1 2 3 4 5 8 ]

1 > 2   ≠> stop

Result: [1 2 3 4 5 8]``````

The algorithm shown below is a slightly optimized version to avoid swapping the `key` element in every iteration. Here, the `key` element will be swapped at the end of the iteration (step).

``````    InsertionSort(arr[])
for j = 1 to arr.length
key = arr[j]
i = j - 1
while i > 0 and arr[i] > key
arr[i+1] = arr[i]
i = i - 1
arr[i+1] = key``````

Here is a detailed implementation in JavaScript:

``````function insertion_sort(A) {
var len = array_length(A);
var i = 1;
while (i < len) {
var x = A[i];
var j = i - 1;
while (j >= 0 && A[j] > x) {
A[j + 1] = A[j];
j = j - 1;
}
A[j+1] = x;
i = i + 1;
}
}``````

A quick implementation in Swift is shown below :

``````  var array = [8, 3, 5, 1, 4, 2]

func insertionSort(array:inout Array<Int>) -> Array<Int>{
for j in 0..<array.count {
let key = array[j]
var i = j-1

while (i > 0 && array[i] > key){
array[i+1] = array[i]
i = i-1
}
array[i+1] = key
}
return array
}``````

The Java example is shown below:

``````public int[] insertionSort(int[] arr)
for (j = 1; j < arr.length; j++) {
int key = arr[j]
int i = j - 1
while (i > 0 and arr[i] > key) {
arr[i+1] = arr[i]
i -= 1
}
arr[i+1] = key
}
return arr;``````

insertion sort in c....

``````void insertionSort(int arr[], int n)
{
int i, key, j;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i-1;
while (j >= 0 && arr[j] > key)
{
arr[j+1] = arr[j];
j = j-1;
}
arr[j+1] = key;
}
} ``````

Properties:

• Space Complexity: O(1)

Time Complexity: O(n), O(n* n), O(n* n) for Best, Average, Worst cases respectively.

• Best Case: array is already sorted
• Average Case: array is randomly sorted
• Worst Case: array is reversely sorted.
• Sorting In Place: Yes
• Stable: Yes