Introduction
Same as bubble sort and selection sort, insertion sort is usually treated as one of the basic sorting algorithms, and similarly, it also utilized nest-loop, which means it has the same time complexity as bubble sort and selection sort.
Insertion Sort: How it Works?
Insertion sort starts from the left side of the array as it insert each element start from index 2 to the left side, which is a sorted portion of the array. Since it always keeps an the left part of the array sorted, It has a better performance than other sorting algorithms when dealing with situation that data keep coming continuously.
Implement Insertion Sort in Python
As shown in the code above, insertion sort loop through the array from the second element (index 1) while keeping the arr[i] as the currentValue, and while in the inner loop, it starts from the (i-1) element and iterated in a reversed order until it reaches the head of the array.
The trick in the inner loop is, whenever an element is found to be larger than the currentValue, it’s assigned to it’s next value, or in another word, arr[j] is sign to arr[j + 1]. And at the end of each outer loop, the currentValue is re-assigned to arr[j + 1]. That’s how the insertion is done, by duplicating one element to the right and assign the currentValue (Which is also the border of the sorted portion of this array) to the element that got duplicated.
