Well. After some initial tests with my median value script, it’s not looking good for the random pivot theory at the moment.
The random pivot version of my script is just like the one in post #6, but with this section .
-- The search process is like a Quicksort, but with recursion only occurring on the side containing the median position. It stops when the inner repeat indices cross at that position. Two searches are done when the number of items is even. Since recursion would involve tail calls, a repeat's used here instead.
set l to extractL
set r to extractR
repeat -- Tail call elimination repeat.
set pivot to o's extract's item ((l + r) div 2)
. modified like this:
set rmod to 2 ^ 31 - 1
set multiplier to 7 ^ 5
set x0 to 3 * multiplier mod rmod -- Equivalent to init() with x0 starting at 3.
-- The search process is like a Quicksort, but with recursion only occurring on the side containing the median position. It stops when the inner repeat indices cross at that position. Two searches are done when the number of items is even. Since recursion would involve tail calls, a repeat's used here instead.
set l to extractL
set r to extractR
repeat -- Tail call elimination repeat.
set x0 to x0 * multiplier mod rmod
tell (r - l + 1) to set pivot to o's extract's item ((x0 / 1.0E+9) * it mod it div 1 + l)
The entire random-number process is in-line to eliminate the overhead of handler calls. The difference inside the repeat (equivalent to a recursion in a recursive version) is only seven very simple math operations and a variable setting. And yet the random pivot version generally tends to be slightly slower than the middle-item pivot version. This means that the advantages of randomly chosen pivots must be somewhere between negative and not enough to repay even this paltry investment. I’d expect difference to be even more apparent in a full Quicksort, which does more recursions and, in particular, more at lower levels, where the shorter range lengths would increase the chances of the same pivots being chosen anyway. I will try random pivots with full Quicksorts before dismissing the theory entirely as an old wives’ tale. But not now as I have to go and mow the lawn.