MAX=100000tmp=[Noneforiinrange(MAX)]defmergesort(a,low,hi):'''Merge-Sort algorithm for arrays of up to MAX elements'''globalMAXassert0<=low<=hi<=len(a)<=MAX# conquer phase: do nothing when a[low,hi) has 0 or 1 elementsiflow+1<hi:# divide phase: there are at least two elements in a[low,hi)mid=low+((hi-low)//2)mergesort(a,low,mid)# solve left halfmergesort(a,mid,hi)# solve right halfmerge(a,low,mid,hi)# merge left and right partsdefmerge(a,low,mid,hi):'''merge a[low,mid) and a[mid,hi) into a[low,hi) assumming that the two parts are sorted in ascending order'''globaltmp# copy a[low,hi) to tmp[low,hi)forkinrange(low,hi):tmp[k]=a[k]l,r,k=low,mid,lowwhilek!=hi:ifl==mid:# a[low,mid) has been processeda[k]=tmp[r];r+=1elifr==hi:# a[mid,hi) has been processeda[k]=tmp[l];l+=1else:# there are elements in each part to be processediftmp[l]<=tmp[r]:# next element in the left is not worse than next element in# the right part: then process next in left parta[k]=tmp[l];l+=1else:# element in the left is worse than next element in the right# part: then process next in right parta[k]=tmp[r];r+=1k+=1
Comments (0)
HTTPSSSH
You can clone a snippet to your computer for local editing.
Learn more.