Insertion Sort - using Python

Talk about Algorithms and sorting comes to mind at first as it is the king of algorithms. Not only because there are many sorting algorithms but sorting is the fundamental operation in computing. Sorting means arranging items in some specific order and we see these all the times when working on our files or folder and working in database when we need records in some certain fashion. Sorting also find its use in searching and other algorithms.

There are many sorting algorithms and we will describe each algorithm and its implementation one post at a time.

Insertion sort

Insertion Sort is one of the simplest sorting algorithm. It is same as we sort  cards in our hand. We look at cards from left to right pick the unsorted card and insert it at correct position.

Explanation

For explaining the insertion sort algorithm we have taken the below unsorted list having 5 elements.

5

1

3

2

4

On first Iteration Second element will be compared with the first element it is smaller than first element they are swapped resulting in below list

1

5

3

2

4

  

On second iteration 3rd element will be checked against 1st and 2nd element and below list is formed.

1

3

5

2

4

And so on till the last element...

1

2

3

5

4

  

Final sorted list

1

2

3

4

5

Implementation

__author__ = 'Dharmjit'
def InsertionSort(list):
    for index in range(1,len(list)):
        curr = list[index]
        position = index

        while position > 0 and list[position-1] > curr:
            list[position] = list[position-1]
            position = position - 1

        list[position] = curr
    return list

l = [2,1,5,3,9,6,7]
print(InsertionSort(l))
[1,2,3,5,6,7,9]

Time complexity

Best Case Scenario:- If the list is already sorted the insertion algorithm runs in O(n) time which is linear

Worst Case Scenario:- When the List is sorted in reverse order, it will take o(n^2) time which is quadratic.