O algoritmo abaixo faz o que ?

from array import array
A = array('l',[1,3,2,8,5,7,4,9])

def transform_array(A):
    for j in range(1,len(A)):
        key = A[j]
        i = j -1
        while (i>=0) and (A[i]>key):
            A[i+1] = A[i]
            i = i - 1
        A[i+1] = key
Código fonte

O algoritmo abaixo faz ordenação do vetor A

# importação do módulo array
from array import array

# criação de um vetor de inteiros longos 'l'
# com N valores desordenados
A = array('l',[1,3,2,8,5,7,4,9])

# metodo de ordenação
def sort_array(A):
    for j in range(1,len(A)):       # j = 2,3,4,...,N-1

        key = A[j]                  # valor chave em A[j]
        i = j -1                    # i == valor a esquerda da chave 
        while (i>=0) and (A[i]>key):
            # i vai diminuir ate achar um valor maior que a chave

            # ou ate atingir o inicio do vetor
            print A,'i=',i,'A[i]=',A[i],'key=',key # debug
            A[i+1] = A[i]
            i = i - 1
        A[i+1] = key


print
print 'antes',A
sort_array(A)
print 'depois',A

Execução do algoritmo

array('l', [1, 3, 2, 8, 5, 7, 4, 9]) j= 1 i= 0 key= 3
array('l', [1, 3, 2, 8, 5, 7, 4, 9]) j= 2 i= 1 key= 2
array('l', [1, 3, 2, 8, 5, 7, 4, 9]) i= 1 A[i]= 3 key= 2
array('l', [1, 2, 3, 8, 5, 7, 4, 9]) j= 3 i= 2 key= 8
array('l', [1, 2, 3, 8, 5, 7, 4, 9]) j= 4 i= 3 key= 5
array('l', [1, 2, 3, 8, 5, 7, 4, 9]) i= 3 A[i]= 8 key= 5
array('l', [1, 2, 3, 5, 8, 7, 4, 9]) j= 5 i= 4 key= 7
array('l', [1, 2, 3, 5, 8, 7, 4, 9]) i= 4 A[i]= 8 key= 7
array('l', [1, 2, 3, 5, 7, 8, 4, 9]) j= 6 i= 5 key= 4
array('l', [1, 2, 3, 5, 7, 8, 4, 9]) i= 5 A[i]= 8 key= 4
array('l', [1, 2, 3, 5, 7, 8, 8, 9]) i= 4 A[i]= 7 key= 4
array('l', [1, 2, 3, 5, 7, 7, 8, 9]) i= 3 A[i]= 5 key= 4
array('l', [1, 2, 3, 4, 5, 7, 8, 9]) j= 7 i= 6 key= 9

antes  array('l', [1, 3, 2, 8, 5, 7, 4, 9])
depois array('l', [1, 2, 3, 4, 5, 7, 8, 9])

Código "assembler" do algoritmo: dis.disassemble(sort_array.func_code)

Algoritmo Assembler Numero de Instruções Numero de Repetições
for j in range(1,len(A)): 
  5           0 SETUP_LOOP             129 (to 132)
              3 LOAD_GLOBAL              0 (range)
              6 LOAD_CONST               1 (1)
              9 LOAD_GLOBAL              1 (len)
             12 LOAD_FAST                0 (A)
             15 CALL_FUNCTION            1
             18 CALL_FUNCTION            2
             21 GET_ITER            
        >>   22 FOR_ITER               106 (to 131)
             25 STORE_FAST               2 (j)
10 N vezes
 key = A[j] 
  6          28 LOAD_FAST                0 (A)
             31 LOAD_FAST                2 (j)
             34 BINARY_SUBSCR       
             35 STORE_FAST               3 (key)
4 N-1 vezes
 i = j -1 
  7          38 LOAD_FAST                2 (j)
             41 LOAD_CONST               1 (1)
             44 BINARY_SUBTRACT     
             45 STORE_FAST               1 (i)
4 N-1 vezes
 while (i>=0) and (A[i]>key): 
  8          48 SETUP_LOOP              63 (to 114)
        >>   51 LOAD_FAST                1 (i)
             54 LOAD_CONST               2 (0)
             57 COMPARE_OP               5 (>=)
             60 JUMP_IF_FALSE           14 (to 77)
             63 POP_TOP             
             64 LOAD_FAST                0 (A)
             67 LOAD_FAST                1 (i)
             70 BINARY_SUBSCR       
             71 LOAD_FAST                3 (key)
             74 COMPARE_OP               4 (>)
        >>   77 JUMP_IF_FALSE           32 (to 112)
             80 POP_TOP
13 2+3+4+...+N vezes
  A[i+1] = A[i] 
  9          81 LOAD_FAST                0 (A)
             84 LOAD_FAST                1 (i)
             87 BINARY_SUBSCR       
             88 LOAD_FAST                0 (A)
             91 LOAD_FAST                1 (i)
             94 LOAD_CONST               1 (1)
             97 BINARY_ADD          
             98 STORE_SUBSCR
8 N*(N-1)/2 vezes
  i = i - 1 
 10          99 LOAD_FAST                1 (i)
            102 LOAD_CONST               1 (1)
            105 BINARY_SUBTRACT     
            106 STORE_FAST               1 (i)
            109 JUMP_ABSOLUTE           51
        >>  112 POP_TOP             
            113 POP_BLOCK
7 N*(N-1)/2 vezes
 A[i+1] = key 
 11     >>  114 LOAD_FAST                3 (key)
            117 LOAD_FAST                0 (A)
            120 LOAD_FAST                1 (i)
            123 LOAD_CONST               1 (1)
            126 BINARY_ADD          
            127 STORE_SUBSCR        
            128 JUMP_ABSOLUTE           22
        >>  131 POP_BLOCK           
        >>  132 LOAD_CONST               0 (None)
            135 RETURN_VALUE
10 N-1 vezes

Complexidade é a somatória da coluna No de repetições que é O(n**2).

Onde n**2 quer dizer n elevado ao quadrado!