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