Pythonic style for stepping through two lists and avoiding idx?

Question

(Before I begin, let us presuppose this is an interview question, and I am intended to avoid merely calling sorted.)

I have this working Python code:

def merge_sorted_lists(left, right):
    leftlen = len(left)
    rightlen = len(right)
    leftidx = 0
    rightidx = 0
    newlist = []
    while leftidx < leftlen or rightidx < rightlen:
        if rightidx == rightlen or left[leftidx] <= right[rightidx]:
            newlist.append(left[leftidx])
            leftidx += 1
        elif leftidx == leftlen or right[rightidx] < left[leftidx]:
            newlist.append(right[rightidx])
            rightidx += 1
    return newlist

I'm a long time C++ programmer who has recently learned enough Python to know that this "smells" very un-Pythonic with the prolific usage of idx. Is there a more elegant way to iterate through two lists when the advancement of the iterator needs this fine-tuned control?

Answer 1

Uh, for a first guess, I'd start out by trying to use generators instead. And I'm using yield instead of constructing a list because a) generators can be infinite and b) hey, once you start using a generator, might as well use generators all the way down.

def merge(left,right): 
    left = iter(left)
    right = iter(right)
    left_val = next(left)
    right_val = next(right)
    try:
        while True:
            if left_val <= right_val:
                yield left_val
                left_val = next(left) #left.next() in python2
            else:
                yield right_val
                right_val = next(right)
    except StopIteration: #I have exhausted one of the iterators
        if left_val <= right_val:
            #left list depleted
            yield right_val
            for i in right: yield i #or use yield from right, if your python is fancy enough
        else:
            #right list depleted
            yield left_val
            for i in left: yield i 

In [2]: f = merge([0,4,17],[2,4,5,6,6,6])
In [3]: list(f)
Out[3]: [0, 2, 4, 4, 5, 6, 6, 6, 17]

Answer 2

I understand that you would like to avoid using "sorted" because you want a solution that better describes the algorithm, but I honestly think that the pythonic solution requires it.

def merge_sorted_lists(left,right):
    return sorted(left+right)

For a non-pythonic solution that exposes a reasonable algorithm without tracking indices, you could try this recursive solution:

def merge_sorted_lists(left,right,acc=[]):
    if not left:
        return acc + right
    if not right:
        return acc + left
    if left[0] < right[0]:
        return merge_sorted_lists(left[1:],right,acc=acc+[left[0]])
    else:
        return merge_sorted_lists(left,right[1:],acc=acc+[right[0]])

This one is quite a few lines longer than my other solution and long inputs could overwhelm the stack.