3. Insertion Sort #

Created Sunday 05 January 2020

• Let the left part be sorted. Initially of length 1.
• Insert the first array of the unsorted side to the appropriate position(using shifting, i.e adjacent swapping), this takes O(size of sorted), in the worst case.
• Move the divider by 1.

Hence worst case time complexity is 1 + 2 + … + n = O(n^2^).

• Best case scenario for Insertion sort: When array is already sorted, each element is already at the sorted position. No swapping at all. All we do is checking n times.

Best case: O(n) - because it is naturally adaptive. Worst case: O(n^2^)