Naive merge sort implementation

merge.py

def merg(a, b):
    # This method takes care of merging two lists while maintaining it sorted.
    # Hence, it must only return the resulting merged list, not the indices i
    # and j.
    c = [None] * int(len(a) + len(b))
    i = 0
    j = 0
    k = 0 # This will take care of where we are placing the new elements

    # i and j must be strictly less than the lengths, otherwise they'll overflow
    # Example: for len(a) = 10, i = 10 is out-of-bounds since indices go from 0
    # to 9.
    while i < len(a) and j < len(b):
        if a[i] < b[j]:
            c[k] = a[i]
            i = i+1
            # Don't return i
        else:
            c[k] = b[j]
            j = j+1
            # Don't return j

        k += 1

    # It might happen that we placed all elements from "b" but there are still
    # some "a" elements left. Let's place them where:
    while i < len(a):
        c[k] = a[i]
        i = i+1
        k = k+1

    # Same rationale here but placing "b" elements this time
    while j < len(b):
        c[k] = b[j]
        j = j+1
        k = k+1

    return c


def msort(x):
    if len(x) == 1:
        return x
    else:
        lx = int(len(x)/2) # No need to round. int(x) already makes it an integer
        A = x[:lx] # Empty left boundary makes the slice start from the beginning
        B = x[lx:] # Empty right boundary makes the slice goes until the end
        A = msort(A)
        B = msort(B)
        return merg(A, B)


def main():
    import random
    random.seed(0)
    x = range(10)
    random.shuffle(x)

    print msort(x)

if __name__ == '__main__':
    main()