Demystifying Insertion Sort. Upgrade Your Sorting Game! | by Radian Krisno | Dec, 2020
At this point, most of you might agree that the operations of for Insertion Sort are not as intuitive compared to the ones for Bubble Sort and Selection Sort. Despite this condition, Insertion Sort performs better Bubble Sort and Selection Sort in almost every case. The best case for Insertion Sort happens when the array is already sorted. So, the only required comparisons are the ones between the new element that is inserted into the array. That’s why we only need to do 1 pass which leaves us with O(n) time complexity.
For the worst case, it happens when the array is in reverse order. In this case, we need to compare all the elements and go through each iteration once. The total number of comparisons is:
1 + 2 + … + (n-3) + (n-2) + (n-1) = n(n-1)/2
This might seems familiar and this brings us to O(n²) time complexity for the worst case. In the average case, half of the elements of the sorted array are smaller and the remaining half are greater than the inserted element. This leads us to compare only half of the array in every pass. Then the total number of comparisons is half of the worst case.
1/2 + 2/2 + … + (n-3)/2 + (n-2)/2 + (n-1)/2 = n(n-1)/4
This still gives us O(n²) time complexity for the average case. However, the number of comparisons is approximately half of the Bubble Sort for the average case.
Read More …