Interesting blog post about how this could be done in Haskell using a suitable mergesort (or quicksort): http://apfelmus.nfshost.com/articles/quicksearch.html h

Interesting blog post about how this could be done in Haskell using a suitable mergesort (or quicksort): http://apfelmus.nfshost.com/articles/quicksearch.html http://apfelmus.nfshost.com/articles/quicksearch.html (pointed out in a similar discussion some time ago). Having used Haskell in university only, articles like this really make me want to revisit the language. (Algorithms aside, the full sort of 10M numbers, apparently using an underlying C implementation, looks stunishingly slow: Given at most 240M comparisons for merge-sorting the array, taking 10s would mean at throughput only 24M items per sec, bad memory access pattern at play maybe?)