To pick pivot selection methods, I tested on a list of English word with
compare.py. The most promising were last, middle, and random.
For each, the input was:
"Algorithms are the backbone of computer science"
They all output:
"Aghilmorst aer eht abbcekno fo cemoprtu cceeins"
Baseline for Testbench
I ran each 1000 times so that time would actually display something, which
incurs overhead from the shell:
> /usr/bin/time sh -c 'for x in `seq 1 1000`; do cat <sentence>/dev/null; done'
0.46user 0.18system 0:00.61elapsed 104%CPU (0avgtext+0avgdata 3456maxresident)k
0inputs+0outputs (0major+139191minor)pagefaults 0swaps
Select the last location for the pivot: between the last to elements.
> /usr/bin/time sh -c 'for x in `seq 1 1000`; do ./last <sentence>/dev/null; done'
0.73user 0.19system 0:00.90elapsed 102%CPU (0avgtext+0avgdata 3472maxresident)k
0inputs+0outputs (0major+177228minor)pagefaults 0swaps
Put the pivot at floor((lo+hi)/2).
> /usr/bin/time sh -c 'for x in `seq 1 1000`; do ./middle <sentence>/dev/null; done'
0.75user 0.15system 0:00.89elapsed 102%CPU (0avgtext+0avgdata 3448maxresident)k
0inputs+0outputs (0major+178294minor)pagefaults 0swaps
Select a random pivot each time.
> /usr/bin/time sh -c 'for x in `seq 1 1000`; do ./random <sentence>/dev/null; done'
0.75user 0.18system 0:00.90elapsed 102%CPU (0avgtext+0avgdata 3480maxresident)k
0inputs+0outputs (0major+180278minor)pagefaults 0swaps
Words are such small lists that as long as the pivot selection is simple, it
doesn't seem to matter that much for performance. I would use the middle, as it
is simple, and performed best on both this and the theoretical Python test.