On Sun, Mar 26, 2017 at 9:19 AM, Gregory Popovitch
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.