# 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
```

## 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
```

## 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]
```