Merge sort implementation in python giving incorrect result

Question

I am trying to implement the merge sort algorithm described in these notes by Jeff Erickson on page 3. but even though the algorithm is correct and my implementation seems correct, I am getting the input list as output without any change. Can someone point out the anomalies, if any, in it.

def merge(appnd_lst, m):
    result = []
    n = len(appnd_lst)
    i, j = 0, m
    for k in range(0, n):
        if j < n:
            result.append(appnd_lst[i])
            i += 1
        elif i > m:
            result.append(appnd_lst[j])
            j += 1
        elif appnd_lst[i] < appnd_lst[j]:
            result.append(appnd_lst[i])
            i += 1
        else:
            result.append(appnd_lst[j])
            j += 1

    return result


def mergesort(lst):
    n = len(lst)
    if n > 1:
        m = int(n / 2)
        left = mergesort(lst[:m])
        right = mergesort(lst[m:])

        appnd_lst = left
        appnd_lst.extend(right)
        return merge(appnd_lst, m)
    else:
        return lst


if __name__ == "__main__":
    print mergesort([3, 4, 8, 0, 6, 7, 4, 2, 1, 9, 4, 5])

Answer 1

There are three errors in your merge function a couple of indexing errors and using the wrong comparison operator. Remember python list indices go from 0 .. len(list)-1.

* ...
6        if j > n-1:  # operator wrong and off by 1
* ...
9        elif i > m-1: # off by 1
* ...