Proposal: a new implementation for Data.List.sort and Data.List.sortBy, which has better performance characteristics and is more laziness-friendly.

[Evan Laforge]

On Sun, Mar 26, 2017 at 9:19 AM, Gregory Popovitch <greg7mdp at gmail.com> wrote:
> Is there a real need to optimize the sort for already sorted list?

It's useful for data constructors with the precondition that the input
is sorted.  I generally keep things in sorted order, but since
sortedness is not tracked in the type and I'm not willing to face
corruption if a transformation slightly de-sorts the list I just
unconditionally sort the input.  It's nice to have that be relatively
cheap for the common case.

I'm just giving a case where it's useful, not advocating for the
status quo.  I don't know how to weight the trade-off for a general
purpose sort.  I'd personally be willing to switch to a specialized
sort that works well on mostly sorted input if it made a performance
difference.