Merge 3 sorted list in a single sorted list

merge_sorted_lists.py

def merge(a, b, c):
    # Result list
    d = []
    # Indices used for iterating through a, b and c
    i = j = k = 0
    # Calculate lengths just once
    lena, lenb, lenc = len(a), len(b), len(c)

    while i < lena and j < lenb and k < lenc:
        if a[i] <= b[j] and a[i] <= c[k]:
            d.append(a[i])
            i += 1
        elif b[j] <= a[i] and b[j] <= c[k]:
            d.append(b[j])
            j += 1
        elif c[k] <= a[i] and c[k] <= b[j]:
            d.append(c[k])
            k += 1

    if i == lena:
        # a has been iterated through; need to sort b and c
        while j < lenb and k < lenc:
            if b[j] <= c[k]:
                d.append(b[j])
                j += 1
            else:
                d.append(c[k])
                k += 1
        # either b or c has been iterated through; append all
        # the remaining elements from the last list since they are
        # already sorted
        if j < lenb:
            d.extend(b[j:])
        else:
            d.extend(c[k:])
    elif j == lenb:
        # b has been iterated through; need to sort a and c
        while i < lena and k < lenc:
            if a[i] <= c[k]:
                d.append(a[i])
                i += 1
            else:
                d.append(c[k])
                k += 1
        # either a or c has been iterated through; append all
        # the remaining elements from the last list since they are
        # already sorted
        if i < lena:
            d.extend(a[i:])
        else:
            d.extend(c[k:])
    else:
        # c has been iterated through; need to sort a and b
        while i < lena and j < lenb:
            if a[i] <= b[j]:
                d.append(a[i])
                i += 1
            else:
                d.append(b[j])
                j += 1
        # either a or b has been iterated through; append all
        # the remaining elements from the last list since they are
        # already sorted
        if i < lena:
            d.extend(a[i:])
        else:
            d.extend(b[j:])

    return d

if __name__ == '__main__':
    print 'merge() examples'
    print '----------------'
    one = [1, 2, 3], [1, 3, 5], [2, 4, 6]
    print '%s, %s, %s' % one, ' => ', merge(*one)
    two = [1, 2, 3], [4, 5, 6], [7, 8, 9]
    print '%s, %s, %s' % two, ' => ', merge(*two)
    three = [1], [], [3, 5, 6]
    print '%s, %s, %s' % three, ' => ', merge(*three)
    four = [], [], []
    print '%s, %s, %s' % four, ' => ', merge(*four)

output.txt

merge() examples
----------------
[1, 2, 3], [1, 3, 5], [2, 4, 6]  =>  [1, 1, 2, 2, 3, 3, 4, 5, 6]
[1, 2, 3], [4, 5, 6], [7, 8, 9]  =>  [1, 2, 3, 4, 5, 6, 7, 8, 9]
[1], [], [3, 5, 6]  =>  [1, 3, 5, 6]
[], [], []  =>  []