HomeAboutBlogProjects

Insertion Sort Algorithm

21 April, 2019 - 2 min read

Something different today and maybe a lot more times in the future. We started with algorithms at university this term. To understand it better I will try to do short articles about the different topics. The algorithm's short facts can be found at the bottom of the page.

Insertion Sort is an algorithm where one item at a time will be inserted in the correct place through comparing with the item to it’s left. You start with the second element of the array which will be compared with the first one. It’s one of the easier algorithms to implement and really efficient with small or partially pre sorted arrays as input. Insertion Sort does not need additional space so it works „in-place“. The Best-Case 𝓞(n) is achieved when the array is already presorted. The Average and Worst Case of Insertion Sort is 𝓞(n²) because if your input arrays is in reversed order you have to compare every single item to put it in the front of the array. The algorithm is an online algorithm which can run while new data keeps coming in. It’s able to do so because of its left side which tends to be sorted already.

Pseudocode

INSERTIONSORT(A)
for i = 2 to A.length do
	toBeSorted = A[i]
	j = i
	while j > 1 and A[j-1] > x do
		A[j] = A[j - 1]
		j = j - 1
	A[j] = x

Example

Input 	<5,3,4,1,2>
1st 	<3,5,4,1,2>
2nd 	<3,4,5,1,2>
3rd 	<1,3,4,5,2>
4th 	<1,2,3,4,5>

JavaScript implementation

function insertionSort(arr) {
    for(var i = 1; i < arr.length; i++) {
		// saves the current Value to compare
        var currentVal = arr[i];
		// go into the for-loop only if j is still greater than 
		// 0 AND the item before is greater than currentVal
        for(var j = i - 1; j >=  0 && arr[j] > currentVal; j--){
            arr[j+1] = arr[j];
        }
        arr[j+1] = currentVal;
    }
    return arr;
}

tl:dr

  • One item at a time
  • Start with the second element - compare it with the first one
  • easy to implement
  • really efficient with small or partial pre sorted input arrays
  • does not need additional space
  • Best Case only achieved when array already in sorted position 𝓞(n)
  • Time complexity in average and worst case are both 𝓞(n²)
  • Insertion sort is an online algorithm