On Mon, Dec 21, 2015 at 3:30 PM John Cowan <xxxxxx@mercury.ccil.org> wrote:

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)?

No, I'm asking for a weaker property, that the sorting algorithm refrain from making any random decisions. "Non-randomized" might be a clearer term. Merge sort and heap sort are the classic non-randomized O(n log n) sorting algorithms. Quick sort is of course randomized.

The stronger property you're asking about is usually called "data-obliviousness." Data-oblivious sorting algorithms actually do exist, and are an active research subject. See e.g. "Randomized Shellsort: A Simple Data-Oblivious Sorting Algorithm" by Goodrich:
http://arxiv.org/pdf/0909.1037.pdf

It's an interesting subject, but I don't think these algorithms are essential enough to go in a SRFI.

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.

So introsort is a curious case of an algorithm which is both randomized and also has a O(n log n) worst-case time bound. While it satisfies the letter of my request, it doesn't really satisfy the spirit. What I really want is a way for a programmer to insist on a predictable non-random run time.

Kevin