From python docs.
I have found the algorithm in quite a few places such as here, here and here. None of them have mentioned the name of the algorithm.
I need to give a reference for a paper so please point me in the right direction.
Asked
Active
Viewed 450 times
3
-
1This is a classic, and probably has no name, and is not python specific. – Programmer Person May 01 '15 at 04:35
-
So can I just provide links as references? (I'm new to the field) – rohithpr May 01 '15 at 04:36
-
2"Standard merge algorithm of sorted list using heaps" – Programmer Person May 01 '15 at 04:38
-
1http://en.wikipedia.org/wiki/Merge_algorithm – wim May 01 '15 at 04:41
2 Answers
4
This is known as "Multiway merging" and is described by Donald Knuth in The Art of Computer Programming, Volume III - Sorting and Searching, section 5.4.1.
orlp
- 112,504
- 36
- 218
- 315
-
[Found it](https://books.google.co.in/books?id=cYULBAAAQBAJ&pg=PA251&lpg=PA251&dq=Multiway+merging+Donald+Knuth+in+The+Art+of+Computer+Programming,+Volume+III+-+Sorting+and+Searching,+section+5.4.1&source=bl&ots=KJysJgOn-K&sig=Tl_Ob26ILod8G7fzohdAqMyJFts&hl=en&sa=X&ei=QAdDVYffGYSwmAW8_YDAAQ&ved=0CC4Q6AEwAg#v=onepage&q=Multiway%20merging%20Donald%20Knuth%20in%20The%20Art%20of%20Computer%20Programming%2C%20Volume%20III%20-%20Sorting%20and%20Searching%2C%20section%205.4.1&f=false) – rohithpr May 01 '15 at 05:11
-
Great! Thanks for the name. I have Knuth sitting on my shelf, perhaps I should have looked first. (and yeah, +1!). – Programmer Person May 01 '15 at 05:24
0
If you understand merging of sorted lists then that is what this function is basically doing. There is no name for it, other than merging.
As an aside, merge-sort uses a similar routine, generally on two sorted lists. It is why it's called 'merge'-sort.
goelakash
- 2,502
- 4
- 40
- 56