Kevin Wortman scripsit:

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

So that means that the number of exchanges done depends only on n without
regard to the values of the elements?  I don't know of any sorts like that.
How do you make #(5 4 3 2 1) and #(3 3 3 3 3) both do the same number of
exchanges (short of messing about with pointless exchanges)?

> 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.

Yes, but that's about keeping the worst case bounded, not about
keeping the best case bounded.  If that's what you meant, then heap sort
(unstable) and merge sort (stable) are your friends.  Modifying the quick
sort algorithm to do introsort (which watches for a too-deep recursion,
more than 2 log n levels, and switches to heap sort for that partition)
also keeps the worst case bounded.

If someone wants to do the surgery on Olin's code to make it do introsort
(and additionally switch to insertion sort when the partition size is
really small, like 16), that would be greatly appreciated.

--
John Cowan          http://www.ccil.org/~cowan        xxxxxx@ccil.org
The present impossibility of giving a scientific explanation is no proof
that there is no scientific explanation. The unexplained is not to be
identified with the unexplainable, and the strange and extraordinary
nature of a fact is not a justification for attributing it to powers
above nature.  --The Catholic Encyclopedia, s.v. "telepathy" (1913)