Insertion Sort

Here are two ways to do Insertion Sort in python.

def insertion_sort(lst):
 for i in xrange(1,len(lst)):
  j = i
  while j > 0 and lst[j] < lst[j-1]:
   swap(lst, j, j-1)
   j -= 1

def insertion_sort2(lst):
 for i in xrange(1,len(lst)):
  val = lst[i]
  j = i-1
  while j >= 0 and val < lst[j-1]:
   lst[j+1] = lst[j]
   j -= 1
  lst[j+1] = val

Insertion sort provides best case $Ω(n)$ and worst case $O(n^2)$.