Im trying to solve a question of python Data Structures and Sorting, and i meet a question about mergesort, this question ask me make two mergesort and
i just finished one mergesort. so i really need some help for this question. thank you !!!!!!
# This is alternate mergesort
# mergesort(p,q) sorts array a from position p to q
import random
from time import time, clock
c=0
def out(a, n):
for i in range(1, n+1): print a[i],
print '\n'
def mergesort(p, q, t): ## parameter t controls switching betwee merge1 and
if p < q : ## merge2
m = (p+q) / 2;
mergesort(p, m, -t); ## t alternates between + and -
mergesort(m+1, q, -t); ## meaning merge1 and merge 2 alternate
if t>0 : merge1(p, m+1, q+1) ## from level to level in recursion.
else: merge2(p, m+1, q+1)
# merge(p,m+1,q+1) merges the portion of array a from position p to m
# and that from position m+1 to q
def merge1(p, r, q): ## This is the original merge from a to b
global c ## c is a counter
i=p; j=r; k=p;
while i < r and j < q :
c=c+1
if a[i] <= a[j]:
b[k] = a[i]; i=i+1
else : b[k] = a[j]; j=j+1
k=k+1
while i < r :
b[k]= a[i];
i=i+1; k=k+1
while j < q :
b[k] = a[j];
j=j+1; k=k+1
def merge2(p, r, q): # This in the merge from b to a
#
# Fill this part. Merge from b to a
#
#{ main program }
n=input('input n ')
a=[]
for i in range(0,2000): a=a+[int(100*random.random())]
b=[]
for i in range(0,2000): b=b+[a[i]] # a and b have the same set of data
t=clock()
mergesort(1, n, 1)
out(b, n)
print 'time ',clock()-t, 'c=', c
n=raw_input('finished ')
