[Haskell-cafe] Re: (flawed?) benchmark : sort

[Denis Bueno]

On Tue, Mar 11, 2008 at 4:01 AM, Adrian Hey <ahey at iee.org> wrote:
>  > and sorting is
>  > meant to be a permutation, so we happily have the situation where this
>  > has a correct answer: 2.
>
>  > Anything else is incorrect.
>
>  Isn't 3 also a permutation? Why is it incorrect?

Because it is not stable.

The documentation for Data.List.sort says the sort is stable:

    "The sort function implements a stable sorting algorithm."

A stable sort respects the order of equal elements as they occur in
the input list.

-- 
 Denis