Ross, fromList2 takes perhaps 3ms off the time when n=50000.  (It is essentially a two-liner, so I consider this acceptable.)<br><br>Nevertheless, I have slightly improved the performance of the stable heapsort; essentially, when labeling values with their index, the index is left as a lazy thunk, but the computation is organized so computing any index takes O(log n).  The speed increase from fromList . Data.List.sort . toList is still but 40% of the speed increase from the heapsort.<br>

<br>Again, I&#39;d like to propose a compromise: make Data.Sequence.sortBy cmp be either fromList2 . Data.List.sortBy cmp . toList, or use the stable pairing-heap sort, and add a second sorting method, sortBy&#39;, that is unstable but faster.<br>

<br>Times (ms)<br>                       min      mean    +/-sd    median    max<br>to/from list:        113.561  119.800    5.470  118.678  139.390<br>pairing heap:         62.440   67.032    3.861   65.174   80.499<br>
stable pheap:         93.402  102.253   11.854   98.529  158.922<br>
fromList2 . toList:  110.221  118.364    6.525  116.265  136.683<br><br clear="all">Louis Wasserman<br><a href="mailto:wasserman.louis@gmail.com">wasserman.louis@gmail.com</a><br>