分治排序算法，平均时间复杂度nlogn

import random
import sys   

#sys.setrecursionlimit(9)

A=[x for x in range(10000)]
random.shuffle(A)

def merge(A,p,q,r):
    n1 = q - p 
    n2 = r - q
    L  = A[p:q+1]
    R  = A[q+1:r+1]
    L.append(65535)
    R.append(65535)
    i=0
    j=0
    for k in range(p,r+1):
        if L[i]<=R[j]:
            A[k] = L[i]
            i = i+1
        else:
            A[k] = R[j]
            j = j+1

def merge_sort(A,p,r):
    if p<r:
        q = (p+r) / 2 
        print q
        merge_sort(A,p,q)
        merge_sort(A,q+1,r)
        merge(A,p,q,r)
    else:
        return True

merge_sort(A,0,len(A)-1)
print A