Insertion Sort with Python

by igor.ganapolsky

Illustration of insertion sort for input list [5, 2, 4, 6, 1, 3]:

Python code:


def insertion_sort(my_list):
    for i in range(1, len(my_list)):
        key = my_list[i]
        print("key in my_list[" + str(i) + "]:" +  str(key))
        # Insert my_list[i] into the sorted sequence my_list[1.. i-1]
        j = i - 1
        while j >= 0 and my_list[j] > key:
            my_list[j+1] = my_list[j]
            j = j - 1
        my_list[j + 1] = key
        print("now my_list is " + str(my_list))

And to do it in reverse just change

 while j >= 0 and my_list[j] > key 

to

 while j >= 0 and my_list[j] < key 

Here is a video example with Big-O explanation:

Advertisements