import timeit import random # will not be needed in binary search # INSERTION SORT (A, n) def InsertionSort(A, n): # for j = 2 to n for j in range(1, n): # key = A[j] key = A[j] # i = j - 1 i = j - 1 # while i > 0 and A[i] > key while (i >= 0) and (A[i] > key): # A[i + 1] = A[i] A[i + 1] = A[i] # i = i - 1 i = i - 1 # A[i + 1] = key A[i + 1] = key A = [x for x in range(1000)] random.shuffle(A) # will not be needed in binary search t = timeit.Timer('InsertionSort(A, len(A))', 'from __main__ import InsertionSort, A') time = (1000000 * t.timeit(number = 1)) # micro-seconds print "InsertionSort(10**3) takes %0.3f micro-seconds" % time