Weird profiling behaviour

[Brian Huffman]

On Wednesday 26 June 2002 04:19 am, Colin Runciman wrote:
> Could it be that the string-comparison sort simply has less sorting to do
> than the int-comparison sort?  The default definition of sortBy uses
> insertion sort, so if the string-sort input happens to be already sorted
> it takes linear time and if the int-sort input happens to be in
> reverse order  it takes quadratic time.

A question I would like to ask is which compiler and libraries are you using? 
In the December 2001 version of Hugs, sortBy is implemented with the default 
definition of insertion sort. But if you are using ghc, you are probably 
using a quicksort algorithm. (Recently the ghc libraries were switched to use 
mergesort instead, but I'm not sure whether this made it into any of the 
released versions.)

Remember that quicksort behaves quadratically in the worst case, which can 
happen with pre-sorted input. Maybe this can explain why the second round of 
sorting is so slow?

- Brian Huffman