heapq.merge default key?

Question

Refer to the following code copied from solution 4 of this page - https://discuss.leetcode.com/topic/50450/slow-1-liner-to-fast-solutions/2:

    streams = map(lambda u: ([u+v, u, v] for v in nums2), nums1)
    stream = heapq.merge(*streams)

nums2, nums1 are lists of numbers.

Why does heapq.merge by default sort on u+v of the [u+v, u, v] lists? The u+v's across different lists in each generator are indeed in sorted order (because nums2 and nums1 are in ascending order), but I don't get how the heap.merge() knows to merge on u+v, the first element of the lists in the len(nums1) generators.

Answer 1

It's not merely sorting on u+v, it's sorting on the entire [u+v, u, v] list. The standard way that Python compares two ordered collections is by comparing corresponding elements, starting at the lowest index and working up until a pair of corresponding elements are unequal. If one sequence is shorter than the other and the longer sequence consists of the smaller sequence with extra elements, the longer sequence is considered to be the greater.

So that's what happens when you compare a pair of strings, tuples, or lists. And you should make sure that your own custom collection objects behave the same way.

This behaviour comes in very handy when doing complicated sorts, since you just need to create an appropriate tuple in the key function that you pass to .sort or sorted. There are some examples of this at Sort a list by multiple attributes?.