<s> __author__ = "<STR_LIT>" <EOL> def insertion_sort ( seq ) : <EOL> '''<STR_LIT>''' <EOL> for i in range ( <NUM_LIT:1> , len ( seq ) ) : <EOL> j = i <EOL> while j > <NUM_LIT:0> and seq [ j - <NUM_LIT:1> ] > seq [ j ] : <EOL> seq [ j - <NUM_LIT:1> ] , seq [ j ] = seq [ j ] , seq [ j - <NUM_LIT:1> ] <EOL> j -= <NUM_LIT:1> <EOL> return seq <EOL> def insertion_sort_rec ( seq , i = None ) : <EOL> '''<STR_LIT>''' <EOL> if i == None : i = len ( seq ) - <NUM_LIT:1> <EOL> if i == <NUM_LIT:0> : return i <EOL> insertion_sort_rec ( seq , i - <NUM_LIT:1> ) <EOL> j = i <EOL> while j > <NUM_LIT:0> and seq [ j - i ] > seq [ j ] : <EOL> seq [ j - <NUM_LIT:1> ] , seq [ j ] = seq [ j ] , seq [ j - <NUM_LIT:1> ] <EOL> j -= <NUM_LIT:1> <EOL> return seq <EOL> def test_insertion_sort ( ) : <EOL> seq = [ <NUM_LIT:3> , <NUM_LIT:5> , <NUM_LIT:2> , <NUM_LIT:6> , <NUM_LIT:8> , <NUM_LIT:1> , <NUM_LIT:0> , <NUM_LIT:3> , <NUM_LIT:5> , <NUM_LIT:6> , <NUM_LIT:2> , <NUM_LIT:5> , <NUM_LIT:4> , <NUM_LIT:1> , <NUM_LIT:5> , <NUM_LIT:3> ] <EOL> assert ( insertion_sort ( seq ) == sorted ( seq ) ) <EOL> assert ( insertion_sort_rec ( seq ) == sorted ( seq ) ) <EOL> if __name__ == '<STR_LIT:__main__>' : <EOL> test_insertion_sort ( ) </s>
