Serge D. Mechveliani
Wed, 3 Apr 2002 09:35:51 +0400
Glenn G. Chappell <email@example.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
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.