# sort inefficiency

**Serge D. Mechveliani
**
mechvel@botik.ru

*Wed, 3 Apr 2002 09:35:51 +0400*

Glenn G. Chappell <ggchappell@yahoo.com> writes
>* 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?
*
The Standard library specifies only the map related to the name
`sort'. This map can be described, for example, via sort-by-insertion
program.
And the algorithm choice is a matter of each particular
implementation. Implementation has right to change the algorithm.
For example, I tried once to argue with GHC for incorporating the
mergeSort algorithm for `sort'.
But they have some version of quickSort which is said faster on
average and O(n^2) in the worst case.
Disliking this n^2 hazard, I overload `sort' with my_sort.
-----------------
Serge Mechveliani
mechvel@botik.ru