Write a function McrgeSortx that implements merge sort on a

Write a function McrgeSort(x) that implements merge sort on a list of numbers. Then generate random lists of numbers of lengths 10, 50, 100, 500, 1000, 5000, 10,000, and 50,000. Measure the time it takes to perform a sort, and make a table of sorting time as a function of list length. Use the following template as a starting point. def mcrgc_list(Alist.Blist): Clist = [] while len(Alist)>0 and len(Blist)>0: # Run so long as neither list is empty. if Alist[0]

Solution

from time import *
from math import *
import random
def merge_list(Alist,Blist):
   Clist = []
   while(len(Alist)>0 and len(Blist)>0):
       if Alist[0]<=Blist[0]:
           nval = Alist.pop(0)
       else:
           nval = Blist.pop(0)
       Clist.append(nval)
   if len(Alist)==0:
       Clist.extend(Blist)
   else:
       Clist.extend(Alist)
   return Clist

def merge_sort(vals):
   nvals = len(vals)
   if nvals==1:
       return vals
   else:
       nhalf = int(floor(nvals/2))
       return merge_list(merge_sort(vals[0:nhalf]),merge_sort(vals[nhalf:]))

ranges = [10,50,100,500,1000,5000,10000,50000]
print \"Range\\tTime\"
out = \"{0}\\t{1}\"
# loop through each range.
for i in ranges:
   tstart = time()
   # perform merge sort on a random genereted list of a range in ranges.
   merge_sort(random.sample(range(i),i))
   tend = time()
   ctime = tend - tstart
   print out.format(i,ctime)

\"\"\"

sample output

\"\"\"