[Gcl-devel] Efficiency of sort

[Stavros Macrakis]

The list sort function in gcl 2.5.0 calls the predicate approximately
twice as many times as necessary.  This is because it checks both a<b
and b<a at every choice point, presumably because it wants to exclude
the a=b case (for stability?).  But (a) sort does not guarantee
stability; (b) I don't think the test is even necessary for stability.
(Am I wrong?)

This matters because sort is often called with expensive predicates.

The solution is simple: in list-merge-sort, comment out the clauses:

    ((funcall predicate key-left key-right) (return l))
and
    ((funcall predicate key-left key-right) (go left))