def mergesort( array ):
# array is a list
#base casee
if len(array) <= 1:
return array
else:
split = int(len(array)/2)
#left and right will be sorted arrays
left = mergesort(array[:split])
right = mergesort(array[split:])
sortedArray = [0]*len(array)
#sorted array "pointers"
l = 0
r = 0
#merge routine
for i in range(len(array)):
try:
#Fails if l or r excede the length of the array
if left[l] < right[r]:
sortedArray[i] = left[l]
l = l+1
else:
sortedArray[i] = right[r]
r = r+1
except:
if r < len(right):
#sortedArray[i] = right[r]
#r = r+1
for j in range(len(array) - r-l):
sortedArray[i+j] = right[r+j]
break
else:
#sortedArray[i] = left[l]
#l = l+1
for j in range( len(array) - r-l):
sortedArray[i+j] = left[l+j]
break
return sortedArray
|
|||||||||
|
First of all, the code suffers a very typical problem. The single most important feature of merge sort is stability: it preserves the order of the items which compare equal. As coded,
of two equals the
(or I don't think that
Of course here
Naked |
|||||
|