[bjoli]

That brings up memories! I did the same thing. We had to sort a million integers in the range 0-1000 (exclusive range). I did a counting sort, and beat every other solution handily.

In my case, though, the teacher disqualified my solution since the resulting lists didn't contain the same fixnums as the one i sorted, which I argued was stupid.

In the end I implemented a merge sort with some tricks and won anyway.

[waterhouse]

The same fixnums!? Fixnums are distinct from bignums in that they're small enough to fit in a machine word and therefore don't need to be objects allocated in the heap... Was this an odd implementation wherein fixnums were put into the heap anyway?

[bjoli]

Nope. This was in PLT scheme. Fixnums were eq? to other fixnums, meaning they satisfied the most basic equality.

Arguing was futile. When we started benchmarking very large lists, the counting sort was the only one that did it in reasonable time. Despite being disqualified.