Bucket/Pigeonhole sort basic idea:

• finite and normally few possible values of keys, for example
  • numeric: 0 to 9
  • week days: monday, tuesday, wednesday, thursday, friday, saturday, sunday
  • months: january to december
• each key value maps to an index into the array of buckets/pigeonholes
• one bucket (pigeonhole) per key value
• sorting algorithm:
  • phase-1: move each entry from the input sequence to the corresponding bucket (say queue) in the array of buckets
  • phase-2: move entries of each bucket, in the required order, to the end of the output sequence
• time complexity:
  • bucket sort runs in time O(n) , assuming number of buckets is not large.

See bucket/pigeonhole sort example below,