Integer Pigeonhole Sort in Ruby

Overview

Integer Pigeonhole Sort is an O(n) solution for sorting a list of n integers from 0 to n-1 with no duplicates. For this specific case the order of the original array does not matter and in fact is not even used, but rather a new array is generated with the correct ordering.

Concise

def integer_pigeonhole_sort(a)
  [*0..a.length-1]
end

u = (0..19).to_a.sort{ rand() - 0.5 }[0..19]
p u

s = integer_pigeonhole_sort(u)
p s
integer_pigeonhole_sort.rb

Verbose

# Integer Pigeonhole Sort
#
# Input: A sequence of numbers from 0 to N in any order.
# Output: An ordered sequence from smallest number to largest.
#
def integer_pigeonhole_sort(numbers)
  sorted = []

  numbers.length.times do |i|
    sorted << i
  end

  sorted
end

# Generate array from 0 to 19 in random order.
unsorted = (0..19).to_a.sort{ rand() - 0.5 }[0..19]
puts unsorted.inspect

# Sort.
sorted = integer_pigeonhole_sort(unsorted)
puts sorted.inspect
integer_pigeonhole_sort_verbose.rb

Sample Input and Output

$ ruby integer_pigeonhole_sort.rb
[19, 16, 11, 6, 12, 8, 5, 18, 7, 10, 2, 1, 15, 17, 0, 13, 3, 9, 14, 4]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]

Further Reading