# Mergesort and validation

I have written an implementation of a Mergesort in Python3. An Ideone with the implementation is available. Any suggestions for improvement or any criticisms?

def merge(a, aux, lo, mid, hi):
assert isSorted(a, lo, mid)
assert isSorted(a, mid+1, hi)

for k in range(lo, hi+1):
aux[k] = a[k]

i, j = lo, mid + 1
for k in range(lo, hi+1):
print("i = ",i, ", j = ",j)
if i > mid:
a[k] = aux[j]
j += 1
elif j > hi:
a[k] = aux[i]
i += 1
elif aux[i] < aux[j]:
a[k] = aux[i]
i += 1
else:
a[k] = aux[j]
j += 1
assert isSorted(a, lo, hi)

def sort(a, aux, lo, hi):
if (lo >= hi): return a
mid = math.floor(lo + (hi-lo) / 2)

sort(a, aux, lo, mid)
sort(a, aux, mid+1, hi)
merge(a, aux, lo, mid, hi)

def merge_sort(a):
aux = [0] * len(a)
sort(a, aux, 0, len(a)-1)
assert isSortedArray(a)

def isSorted(a, lo, hi):
for i in range(lo, hi):
if a[i+1] < a[i]:
return False
return True

def isSortedArray(a):
for i in range(0, len(a)-1):
if a[i+1] < a[i]:
return False
return True

• You should generally use better variable names than that. Something about python seems to make people use variable names as short as possible, but anyone reading your code is going to have a hard time, because they have to work out what the heck aux is. Commented Nov 1, 2014 at 7:57
• @JamesJenkinson aux means auxiliary array. I thought that was clear, but I guess auxiliary would have been clearer. Thanks! Commented Nov 2, 2014 at 2:22

• You could avoid typing +1 and -1 in a few places by using inclusive-exclusive ranges, like 200_success nicely explained answering to your other question.
• isSortedArray should call isSorted instead of repeating the same code.
• Instead of math.floor(lo + (hi-lo) / 2) you could use integer division (lo + hi) // 2 so you don't need to import math.
• Passing around aux just to have a place for temporary data in merge seems like an unnecessary complication. Instead you could just take two slices from a and merge them back into a.