#!/usr/bin/env python2

import random


def insertion_sort(l):
  sz = len(l)
  for i in range(sz):
    if i == 0: continue
    j = i-1
    while l[i] < l[j] and j > -1:
      j -= 1
    l.insert(j+1, l.pop(i))
  return l

l = list(reversed(range(1000)))
#random.shuffle(l)
print l
print insertion_sort(l)