question about 'sort' algorithm

David Roundy
Wed, 2 Oct 2002 07:01:50 -0400

I was wondering if anyone knows what sort of algorithm the 'sort' function
in the List module actually uses?  In "The Haskell 98 Library Report", they
give an insertion sort implementation, but I find it hard to believe that
the library actually uses insertion sort.

Basically, I need O(n log n) sorting, and this is a bit awkward to
accomplish efficiently with lists.  I would have thought that this
awkwardness should be dealt with in the standard library, but seeing an
O(n^2) algorithm in the description troubles me.
David Roundy