[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Change Emacs 'sort' API to use three-way comparison

From: David Kastrup
Subject: Re: Change Emacs 'sort' API to use three-way comparison
Date: Fri, 29 Aug 2014 23:51:56 +0200
User-agent: Gnus/5.13 (Gnus v5.13) Emacs/24.4.50 (gnu/linux)

Paul Eggert <address@hidden> writes:

> One infelicity I noticed in the recent change to 'sort' in the trunk
> is that the new implementation calls its predicate twice for each
> comparison.  This is because the Lisp API says the comparison function
> returns a boolean (nil or non-nil), whereas qsort_r wants the
> comparison function to return a ternary value (-1, 0, or 1). If the
> predicate is expensive, the new Fsort can be twice as slow as the old.
> We could tune it but I don't see how to get it any faster than 1.5x
> slower than before, assuming random input and an expensive comparison
> function.

Can someone give an executive summary why we would be using a "qsort_r"

"sort" sorts a list.  There is really not much of a point in not using a
mergesort here, resulting in a stable sort and requiring only a binary
comparison function.

Quicksorts make sense when sorting arrays.

David Kastrup

reply via email to

[Prev in Thread] Current Thread [Next in Thread]