Is `heapq.merge` stable?

Python Help
3

The docs don’t say so, but two plausible meanings for “stable” are satisfied by merge():

  • If it1 is an input iterator yielding some duplicate values, merge() will produce them in the same order as it1 (intra-iterator stability).

  • If it2 is an input iterator that appears after it1 in the argument list, and produces some value also produced by it1, than all the duplicate values from it1 will be produced before any from it2 (inter-iterator stability).

Note a subtlety: these are true even if reverse=True is passed. Few people realize it, but the same is true of passing reverse=True to list.sort() or sorted(): the original order of equal elements is preserved regardless of whether reverse is in effect. reverse only affects the order of non-equal elements.

6 Likes