Insertion sort in python

Insertion sort, is an efficient algorithm for sorting a small number of elements.

Insertion sort works the way many people sort a hand of playing cards. We start with an empty left hand and the cards face down on the table. We then remove one card at a time from the table and insert it into the correct position in the left hand.

To find the correct position for a card, we compare it with each of the cards already in the hand, from right to left.

Here is the pseudocode for it.

Here is the python version of it

def insertionSort(a):
    for j in range(1, len(a)):  
        key = a[j]
        i = j - 1
        while (i > -1 and a[i] > key): 
            a[i + 1] = a[i]
            i = i - 1
        a[i + 1] = key

    return a

a = [6, 5, 3, 1, 8, 7, 2, 4] 
print insertionSort(a)

Hope this helps :)

Varun Pant

Insertion sort in python  by  Varun Pant