Glenn G. Chappell <[EMAIL PROTECTED]> 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 [EMAIL PROTECTED] _______________________________________________ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell