sort inefficiency

[Serge D. Mechveliani]

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