On Fri, Dec 18, 2015 at 6:20 PM John Cowan <xxxxxx@mercury.ccil.org> wrote:

I mean that the runtime involves no randomness and is O(n log n) without exception.

E.g. vector-deterministic-sort would be prohibited from using quicksort, since quicksort takes O(n log n) expected time, but notoriously may take as much as O(n^2) time with low probability.

This is a concern in real-time systems, where unpredictable run times are a big liability.

Kevin Wortman