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
aux
is. \$\endgroup\$ – James Jenkinson Nov 1 '14 at 7:57aux
means auxiliary array. I thought that was clear, but I guessauxiliary
would have been clearer. Thanks! \$\endgroup\$ – khateeb Nov 2 '14 at 2:22