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 ')

Writing/showing/copying code seems to be made very difficult in the new DaniWeb format!

Double-clicking on the code area will highlight it proberly for copying and pasting.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.