Re: question about 'sort' algorithm

On Wed, Oct 02, 2002 at 07:01:50AM -0400, David Roundy wrote:

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.

It's up to the implementation. GHC and NHC use merge sort, which is O(n log n). Hugs uses insertion sort, but the next release will offer the same version GHC uses.