Inefficient sort implementation

Glenn G. Chappell
Tue, 2 Apr 2002 12:42:18 -0800 (PST)

I am wondering about a design decision in the List module.

To wit: "sort", in both the H98 library report and the Hugs file
List.hs, is implemented using a quadratic sort (insertion sort).

Using the name "sort" certainly suggests that this is a good function
to use for sorting. I would think it is pretty obvious that "sort"
should be implemented using an efficient algorithm. I am thinking
primarily of merge sort, which has O(n log n) worst case behavior,
is stable, and has an elegant and efficient functional implementation.

Certainly insertion sort is good to have around, if one is sorting
data that is nearly sorted already, but I would say insertion sort
is clearly not the best choice (or even a good choice) for a general-
purpose sorting algorithm.

Or am I missing something?

Glenn G. Chappell    <><
Dept. of Mathematical Sciences * Ofc: (907) 474-5736
University of Alaska Fairbanks * Fax: (907) 474-5394

Do You Yahoo!?
Yahoo! Tax Center - online filing with TurboTax