# Insertion sort

I have enrolled for advanced computer algorithm course in winter fall 2013. As a part of required reading, we were asked to understand how the insertion sort works. In the write-up, I will be explaining how does the algorithm works and will provide you a python code of the same.

Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

Lets see an example:

Input list:

5 6 3 1 8 7 2 4

While processing:

5 6 3 1 8 7 2 4
5 6 3 1 8 7 2 4

3 5 6 1 8 7 2 4

1 3 5 6 8 7 2 4

1 3 5 6 8 7 2 4

1 3 5 6 7 8 2 4

1 2 3 5 6 7 8 4

1 2 3 4 5 6 7 8

So the sorted list looks like this:

1 2 3 4 5 6 7 8
# /usr/bin/python
# A program to do insertion sort

def insertion_sort(inp_list):
'''Insertion sort function'''

for i in range(1, len(inp_list)): # => C*n operations, given n is the no of elements in the list
valueToInsert=inp_list[i]     # => C*(n-1) operations
holePos=i                     # => C*(n-1) operations
'''The current index is cached in-order to look if the valueToInsert is less
than the elements in the sorted list.'''
while holePos > 0 and valueToInsert  C *(n-1)*\latex{\sum\limits_{i=0}^holePos i} operations
''' i time(s) is checked whether the valueToInsert is less than the elements
in the sorted list.'''
inp_list[holePos] = inp_list[holePos - 1]  # => C*(n-1)*\latex{\sum\limits_{i=0}^holePos i} operations
holePos = holePos -1                       # => C*(n-1)*\latex{\sum\limits_{i=0}^holePos i} operations
inp_list[holePos] = valueToInsert              # => C*(n-1) operations
return inp_list

def main():
'''Main function'''

inp =[]
s = int(raw_input('How many elements would you like to enter: '))
for x in range(s):
inp.append(int(raw_input('Enter element #' + x+1 + ': ')))
output_list = insertion_sort(inp)
print "Sorted list: ", output_list

if __name__ == "__main__":
main()

Best case (If the list is already sorted complexity becomes): O(n)
Worst case (If the list is sorted in the descending order): O(C *(n-1)*\latex{\sum\limits_{i=0}^n i}) = O(n^2)