There seems to be a renewed interest in sorting and in adaptive sorting. A while ago (pre Haskell 98) I compiled a rather extensive library of sorting routines you may want to look at =09http://www.informatik.uni-bonn.de/~ralf/software.html#sort This includes different versions of mergesort, introspective sort (quicksort with a log n depth bound), heapsort etc. Cheers, Ralf