Mergesort-style Iteration Over Two Iterators In Python

Is there an elegant way in Python to iterate over two iterators in the way that the mergesort algorithm does during the merge phase? What I mean by that is assume that list1 and l

Solution 1:

I would think the easiest way to do this is to have temporary variables, one for each iterator, to store the "current" value from that iterator. Then you can perform comparisons on the two variables instead of fetching from the iterator, which will cause you problems.

# This function dumps one iterator into your list, in case one of the two
# runs out of values.
def dump_iter(iterator, newlist):
  for i in iterator:
    newlist.append(i)
    return newlist

iter1 = # Your first iterator.
iter2 = # Your second iterator.
newlist = []

# Get initial values.
try:
  var1 = iter1.next()
except StopIteration:
  return dump_iter(iter2, newlist)
try:
  var2 = iter2.next()
except StopIteration:
  newlist.append(var1)
  return dump_iter(iter1, newlist)

# Now we actually perform the merge sort.
while True:
  if var1 <= var2:
    newlist.append(var1)
    try:
      var1 = iter1.next()
    except StopIteration:
      newlist.append(var2)
      return dump_iter(iter2, newlist)
  else:
    newlist.append(var2)
    try:
      var2 = iter2.next()
    except StopIteration:
      newlist.append(var1)
      return dump_iter(iter1, newlist)

Here, we're storing the "next" value of each iterator in a variable, which we can look at and compare without triggering the iterator itself. When we add one of the variables to the new list, we replace it by triggering that iterator. Here we're catching StopIteration to know when one of the iterators has run out of data; when that happens, we just dump the remaining contents of the other iterator into our list. (Though we also have to append that variable from the other list.)