Insertion Sort in python

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.

The following table shows the steps for sorting the sequence {3, 7, 4, 9, 5, 2, 6, 1}.

In each step, the key under consideration is underlined.

The key that was moved (or left in place because it was the biggest yet considered) in the previous step is marked with an asterisk.

3  7  4  9  5  2  6  1
3* 7  4  9  5  2  6  1
3  7* 4  9  5  2  6  1
3  4* 7  9  5  2  6  1
3  4  7  9* 5  2  6  1
3  4  5* 7  9  2  6  1
2* 3  4  5  7  9  6  1
2  3  4  5  6* 7  9  1
1* 2  3  4  5  6  7  9

Code Example

def insertionSort(myList):
  
    # Traverse through 1 to len(myList)
    for i in range(1, len(myList)):
  
        key = myList[i]
  
        # Move elements of myList[0..i-1], that are
        # greater than key, to one position ahead
        # of their current position
        j = i-1
        while j >=0 and key < myList[j] :
                myList[j+1] = myList[j]
                j -= 1
        myList[j+1] = key
  
  

myList = [26,78,14,92,57,44,37,58,26]
insertionSort(myList)
print(myList)

When you run this you will see this

>>> %Run insertionSort.py
[14, 26, 26, 37, 44, 57, 58, 78, 92]

Links

Read more at https://en.wikipedia.org/wiki/Insertion_sort

code is available at https://github.com/programmershelp/maxpython/blob/main/code%20example/insertionSort.py