Insertion Sort


Insertion Sort

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 :

![ 8 3 5 1 4 2 ]

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 :

![ 3 8 5 1 4 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 :

![ 3 5 8 1 4 2 ]

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 :

![ 1 3 5 8 4 2 ]

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 :

![ 1 3 4 5 8 2 ]

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]

![ 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

Other Resources:

This article needs improvement. You can help improve this article. You can also write similar articles and help the community.