sample merge sorting algo

merge_sort.py

#!/usr/env python


def merge(A, B, C):
    """ O(n)"""

    i = 0
    j = 0

    for k in range(len(A) + len(B)):

        # If left node items are done, just fill up remaining right node items
        if i == len(A):
            C[k] = B[j]
            j += 1
            continue

        # If right node items are done, just fill up remaining left node items
        if j == len(B):
            C[k] = A[i]
            i += 1
            continue

        # Compare items in left and right node
        if A[i] < B[j]:
            C[k] = A[i]
            i += 1
        else:
            C[k] = B[j]
            j += 1

    return


def merge_sort(l):
    """ Uses Divide and Conquer method to sort a list"""

    # Base case
    if len(l) == 1:
        return

    # split into smaller lists and call recursively.
    # DIVIDE
    left = l[:len(l)//2]
    right = l[len(l)//2:]

    # note - 'left' and 'right' list variables are *necessary*,
    # they store the updated list (l) when merge is called.
    # CONQUER
    merge_sort(left)
    merge_sort(right)

    # merge and update the list with the merge result.
    # COMBINE
    merge(left, right, l)
    # print "Merge of {} and {} gives {}".format(left, right, l)
    return


def main():
    ilist = [4,5,6,2,1,8,9,0]
    merge_sort(ilist)
    print ilist


if __name__ == "__main__":
    main()