Talk:Pigeonhole sort

Python Example

The python example doesnt demonstrate the pigeonhole sort, it shows the counting sort because its incrementing the "hole" array instead of inserting the value of the input array. 188.37.101.41 (talk) 16:25, 21 January 2019 (UTC)Karelian

sort

From the article:

In a certain sense, each pass of Quicksort is a kind of pigeonhole sort with just two pigeonholes (or three pigeonholes if it uses a Dutch National flag partitioning).

However, the Quicksort article does not define Dutch National flag partitioning, and neither does the article include a reference. 137.205.139.228 18:08, 10 June 2007 (UTC)

The statement "one pigeonhole for each key through the range of the original array." is misleading. To the extent the pigeonhole sort represents a hash table using a linear hash function, as with any hash table, collisions have to be handled to avoid loss of data. Much better performance is achieved by scaling the number of pigeon holes proportionate to the number of keys and arranging the linear hash function accordingly. Depending upon the collision handling approach used, e.g. if linear or quadratic hashing is used table size should typically be 1.5 to 2.0 times the number of records to be sorted, while if chained hashing is used (i.e. using linked lists at hash table locations to store multiple collided records) table size should be similar to the number of keys or slightly greater for typical optimal performance. --Copsewood (talk) 21:48, 2 June 2009 (UTC)