Insertion Sort
Insertion sort works similarly as we sort cards in our hand in a card game.
We assume that the first card is already sorted then, we select an unsorted card. If the unsorted card is greater than the card in hand, it is placed on the right, otherwise, to the left. In the same way, other unsorted cards are taken and put in their right place.
A similar approach is used by insertion sort.
The idea is for each iteration, if arr[i] is larger than the anchor item, then arr[i] needs to go to the place before anchor item, and all the items between anchor (including anchor) and arr[i] should move right.
Implementation
Pseudo codes
insertionSort(array)
mark first element as sorted
for each unsorted element X
'extract' the element X
for j <- lastSortedIndex down to 0
if current element j > X
move sorted element to the right by 1
break loop and insert X here
end insertionSort
var insertionSort = function (array) {
for (var i = 1; i < array.length; i++) {
const value = array[i];
for (var j = i - 1; j >= 0 && array[j] > value; j--) {
array[j + 1] = array[j];
}
array[j + 1] = value;
}
};def insertionSort(array):
for step in range(1, len(array)):
key = array[step]
j = step - 1
# Compare key with each element on the left of it until
# an element smaller than it is found
while j >= 0 and key < array[j]:
array[j + 1] = array[j]
j = j - 1
# Place key at after the element just smaller than it.
array[j + 1] = key
data = [9, 5, 1, 4, 3]
insertionSort(data)
print(data)Time Complexity
Best: O(n)
Worst: O(n^2)
Average: O(n^2)