Email list hosting service & mailing list manager

deterministic sorts Kevin Wortman (19 Dec 2015 00:44 UTC)
Re: deterministic sorts John Cowan (19 Dec 2015 02:20 UTC)
Re: deterministic sorts Kevin Wortman (21 Dec 2015 23:07 UTC)
Re: deterministic sorts John Cowan (21 Dec 2015 23:30 UTC)
Re: deterministic sorts Kevin Wortman (15 Jan 2016 00:07 UTC)

Re: deterministic sorts John Cowan 19 Dec 2015 02:20 UTC

Kevin Wortman scripsit:

> The same is true of sort algorithms with deterministic (i.e.
> non-randomized) run times. So, could we add procedures that guarantee a
> deterministic worst case time bound?

I'm not sure what you mean by "deterministic worst case".  I don't know
any sort algorithms that run in a fixed amount of time, whereas the vector
merge sort that underlies stable-sort and stable-sort! has a worst-case
time of O(n log n), the same as its average running time.  I considered
replacing the quick sort with introsort (basically: quick sort to
a certain recursion depth dependent on n, then switch to merge sort
to avoid runaway recursion), but decided it was more work than I could
affort to put into it.  The sample implementations can always be replaced,
as they are not fixed the way the SRFI text is after finalization.

--
John Cowan          http://www.ccil.org/~cowan        xxxxxx@ccil.org
Do I contradict myself?
Very well then, I contradict myself.
I am large, I contain multitudes.
        --Walt Whitman, Leaves of Grass