跟我一起学 - 算法导论 - 递归式

#  encoding: utf-8  
arr = []
def  printTree():
    ac  =  []
    ii  =  0 
     for  r  in  arr :
        c,ss,cc  =  r 
        sc  =  [ '   '   for  i  in  xrange(cc * (c - 1 ))]
         for  i  in  xrange(len(sc)) :
             if  i  %  cc  ==  0 : sc[i] = " │ "  
         # print "ci %s ii %s = %s "%(ci,ii,ii < ci)
         if  ii >= c  : 
            sc  =   "" .join(sc) + " ├─ " + ss + '    '
         else  :
            sc  =   "" .join(sc) + " └─ " + ss
        ii  =  c
        ac.append( sc )
        
     for  r  in  ac[:: - 1 ] :
         print  r
    

def  MERGE(A,p,q,r):
     # print "%s:%s - %s:%s" % (p,q+1,q+1,r+1)
     if  p == q : L  =  [A[p], 10 ** 10 ]
     else  : L  =  A[p:q + 1 ] + [ 10 ** 10 ]

     if  q + 1 == r : R  =  [A[r], 10 ** 10 ]
     else  : R  =  A[q + 1 :r + 1 ] + [ 10 * 10 ]

    i  =  j  =  0
     for  k  in  xrange(p,r + 1 ):
         if  L[i] < R[j] :
            A[k] = L[i]
            i += 1
         else :
            A[k] = R[j]
            j += 1
     #  print "%s:%s = %s \n%s:%s = %s\n\n%s" % ( p,q, L , q+1,r,R, A)


def  MERGE_SORT(A,p,r,c = 1 ):
     if  p < r:
        q  =  (p + r) / 2
        MERGE_SORT(A,p,q,c + 1 )
        MERGE_SORT(A,q + 1 ,r,c + 1 )
        arr.append( (c, " %s - %s "   %  ( A[p:q + 1 ],A[q + 1 :r + 1 ]) ,  3  ) )
         #  Debugging(A,p,q,r, sc )
        MERGE(A,p,q,r)

A = [ 5 , 2 , 7 , 4 , 1 , 3 , 2 , 6 ]
MERGE_SORT(A,0,len(A) - 1 )
print  A
printTree() 

[1, 2, 2, 3, 4, 5, 6, 7]
├─[2, 4, 5, 7] - [1, 2, 3, 6]
│  ├─[1, 3] - [2, 6]
│  │  ├─[2] - [6]
│  │  └─[1] - [3]
│  ├─[2, 5] - [4, 7]
│  │  ├─[7] - [4]
│  │  └─[5] - [2]