Insertion Sort Analysis - Python Implementation

Insertion sort always maintains a sorted sublist at the beginning of a list. New items are then again "inserted" back into the previous sorted sublist such that the sublist remain sorted and it becomes just one item larger.

Time Complexity:
        Worst Case and Average Case: O(n²)
        Best Case: O(n)

It works as the same way we arrange cards.

Look at the example of swapping items in insertion sort below: 

Consider [3, 2, 1]

The loop starts with 3. Since it is the first item in the list there is nothing else to do.

[3, 2, 1]

The next item is 2. It compares 2 to 3 and since 2 is less than 3 it swaps them, first putting 3 in the second position and then placing 2 in the first position.

[2, 3, 1]

The last item is 1. Since 1 is less than 3 it moves 3 over.

[2, 3, 3]

Since 1 is less than 2 it swaps moves 2 over.

[2, 2, 3]

Then it inserts 1 at the beginning.

[1, 2, 3] 

 

Let's see the python implementation of Insertion sort.  def insertion_sort(array): """ Function to do insertion sort. Args: array (List[int]): input array. Returns: array (List[int]): The return value. A sorted list. """ for idx in range(1, len(array)): key = array[idx] j = idx - 1 while j >= 0 and array[j] > key: array[j + 1] = array[j] j -= 1 array[j + 1] = key return array if __name__ == "__main__": arr = [1, 12, 11, 13, 5, 6] print(insertion_sort(arr))