1

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 list2 are in sorted order (let's say ascending, but it doesn't matter). I want to iterate through both lists simultaneously, where the next item returned is the smallest of the two next items from either list. It would also have to handle logic like if list1 is empty:, just return from list2.

Furthermore, I would like the ability to select a specific key to use for comparison, just like Python allows when doing all its standard sorting.

1

1 Answer 1

0

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.)

Not the answer you're looking for? Browse other questions tagged or ask your own question.