One of today's Meditation threads (To push and pop or not to push and pop?
) mentioned "Shift, Pop, Unshift and Push with Impunity!
" which in turn mentioned a paper by Uri Guttman and Larry Rossler called "A Fresh Look at Efficient Perl Sorting".
The link in that node is no longer valid, but it can be found on Uri's site http://www.sysarch.com/ here: http://www.sysarch.com/Perl/sort_paper.html.
The paper is quite old, but sorting hasn't changed much in 5 years! The main reason I am posting it here in Meditations is that this is the first document I have read that made me realise in only a few minutes exactly what the Schwartzian Transform does! It is basically a standard pre-caching sort manouvre, but using a pipeline of anonymous arrays instead of a temporary named hash.
Other than that, the paper is a good refresher of all that sorting algorithm thinking that you can never quite remember from University...
Update: Corrected the spelling of Uri's name - thanks sauoq