Insertion Sort

Builds up the sort by gradually creating a larger left half which is always sorted

taking an element one at a time and inserting it in the correct spot.

 

Insertion Sort Pseudocode

• Start by picking the second element in the array
• Now compare the second element with the one before it and swap if necessary.
• Continue to the next element and if it is in the incorrect order, iterate through the sorted portion (i.e. the left side) to place the element in the correct place.
• Repeat until the array is sorted.

 

function insertionSort(arr) {
    for(var i = 1; i<arr.length; i++){
        var currentVal = arr[i];
        for(var j= i-1; j>= 0 && arr[j]>currentVal; j--){
            arr[j+1]  =arr[j];
        }
        arr[j+1]=currentVal;
    }
    return arr;
}

insertionSort([1,81,2,9,76,4])

 

O(N^) 

as the length of the array grows, you hamve to make n squared number of comparisons.

but if the data is nearly sorted. it is good solution.

it works well in a situation where data is coming in live or streaming and you need to insert it at a moment's notice.

 

 

---

Comparing Bubble, Selection, and Insertion Sort

 

www.toptal.com/developers/sorting-algorithms

Sorting Algorithms Animations

 

 

Algorithm	Time Complexity (Best)	Time Complexity (Average)	Time Complexity (Worst)	Space Complexity
Bubble Sort	O(n)	O(n^)	O(n^)	O(1)
Insertion Sort	O(n)	O(n^)	O(n^)	O(1)
Selection Sort	O(n^)	O(n^)	O(n^)	O(1)

 

 

• They are all roughtly equivalent.
• All have average time complexities that are quadratic
• They are less intuitive.. so need more complex algorithms