What is the algorithm used by python heapq.merge known as?

From python docs .

I found the algorithm in several places like here , here and here . None of them mentioned the name of the algorithm.

I need to link to the paper, so please point me in the right direction.


source to share

2 answers

This is called "multi-user merging" and is described by Donald Knuth in The Art of Computer Programming, Volume III Sorting and Searching, Section 5.4.1.



If you understand merging sorted lists, then this is what this function basically does. There is no name for this other than merge.

As an aside, merge-sort uses a similar procedure, typically on two sorted lists. This is why it is called "merge" -sort.



All Articles