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