4
\$\begingroup\$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.