> random_shuffle looks pretty hairy.

random_shuffle, as usually implemented, is based on swaps (establishing a  
random permutation) -- but one can also think of it as sorting with a  
"broken" comparison function which returns random results, so there may be  
a clever alternative to doing a real sort with an appended random key?

> There's a non-clever way to make any sort stable, which is to add a
> secondary sort key that is the original position in the list.  There
> may be a clever way to do a stable mergesort without knowing the list
> lengths in advance, but I don't know it.

The idea of radix-sort is that one can reduce the problem of sorting on a  
wide key to several sorts on narrow keys -- adding a secondary sort key is  
a bit self-defeating for this use.

The brute-force way to preserve stability is to reverse the reversed list  
in between passes, as used here with integers providing lists (and a pair  
of integers providing a tape):
http://en.literateprograms.org/Merge_sort_(dc)

The clever way (as used with actual tape drives) was to reverse the sense  
of comparison on each pass.

> That leaves only the heap and permutation operations.  I really don't
> know about them.

I'd guess heaps and permutations are essentially swap-based, and that  
swaps imply random access.
(permutations are closely related to insertion/selection-sort, which are  
not so far away from heap sort)

Knuth Vol 3, "Sorting and Searching", might be a good reference.  Anything  
that was good for external sorting with tapes ought to be good with  
lists.  (indeed, being good with tapes implies that one should be able to  
find more cache-friendly implementations than the standard  
singly-linked-list)

> A remarkably large share of the uses of array indexing by numerical
> variables I found in both my Python code and my JavaScript code were
> for some variant of the string.join problem --- given an array of N
> strings, connect them with N-1 commas, except when N=0, in which case
> we should connect them with N=0 commas instead of N-1 = -1 commas.

Squint at it properly, and tail-call optimization becomes an instance of  
string.join: instead of "a,b,c," (where x is a jump and ',' the equivalent  
return) we want to generate "a,b,c".  The dual (context preservation when  
building argument lists) follows the same pattern: we only need to  
save/restore contexts if there are at least two overlapping evaluations.

This may be a practical reason for the last couple of decades' interest in  
monads: we prefer to program in an algebraic, tree-like form (code as well  
as data), while the iron prefers to handle linear sequences of code  
operating on contiguous chunks of data (op x state -> state') -- and  
monads provide machinery to go from tree inputs to flat results in a  
theoretically nice manner.

-Dave