def merge(A, p, q, r):
#    print 'merging (%d, %d, %d)'%(p, q, r)
    L = A[p:q+1]+[float('inf')]
    R = A[q+1:r+1]+[float('inf')]
    i = 0
    j = 0
    for k in range(p, r + 1):
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1


B = [1, 3, 5, 7, 2, 4, 8, 10, 11]
merge(B, 0, 3, 8)
print B


def merge_sort_main(A, p, r):
    if p < r:
        q = int((p + r) / 2.0)
        merge_sort_main(A, p, q)
        merge_sort_main(A, q + 1, r)
        merge(A, p, q, r)

def merge_sort(A):
    merge_sort_main(A, 0, len(A) - 1)


B = range(10, 0, -1)
merge_sort(B)
print B

import time 
import gc

def calc_time(sort_function, array):
    timesum = 0
    gc.collect()
    for i in range(10):
        array_copy = list(array)
        tic = time.time();
        sort_function(array_copy)
        toc = time.time();
        timesum += toc - tic
    return timesum/10



def insertion_sort(A):
    j = 1
    while j < 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
        j = j + 1

print calc_time(insertion_sort, range(1000,1,-1))

import random as rnd

def exper_analysis(sizes):
    results_merge = []
    results_insertion = []
    for i in sizes:
        list1 = range(i)
        rnd.shuffle(list1)
        results_merge.append(calc_time(merge_sort, list1))
        results_insertion.append(calc_time(insertion_sort, list1))        
    return (results_merge, results_insertion)
        
        

import numpy as np
import pylab as pl
%matplotlib inline
pl.clf()
sizes = np.arange(10,700,10)
(y1,y2) = np.array(exper_analysis(sizes))
pl.plot(sizes, y1, 'k.', label = 'Merge sort')
pl.plot(sizes, y2, 'bx', label = 'Insertion sort')
pl.xlabel('Array size')
pl.ylabel('Seconds')
pl.legend(loc = 'upper left')