The faster sort for Data.Sequence is a heapsort based on a pairing heap implementation. The only way I can think of to make it stable is to index the entire sequence and then add indices to the comparisons, which removes almost all of the benefit of the heapsort implementation:<br>
<br>Times (ms) <br> min mean +/-sd median max <br>to/from list: 106.742 111.269 4.831 110.207 138.638<br>pairing heap: 62.896 66.066 2.410 65.433 74.471<br>
stable pheap: 95.600 102.381 5.807 100.744 120.395<br><br>Even worse, the stable heapsort becomes genuinely worse when there's memory to spare; with +RTS -H128m:<br><br>Times (ms)<br> min mean +/-sd median max<br>
to/from list: 53.675 84.407 14.130 86.319 108.553<br>pairing heap: 62.492 77.065 9.649 78.883 104.606<br>stable pheap: 70.437 97.718 15.332 100.548 134.624<br><br>Perhaps the most reasonable compromise would be to include the faster sort method, but name it sortBy' or something else indicating that it is nonstandard. (That still leaves open the question of whether the stable sort method should be the Data.List conversion, or the stable heapsort.)<br>
<br>I had forgotten to mention that zipWith had been modified to a one-liner with mapAccumL, which actually proved faster than my implementation.<br><br clear="all">Louis Wasserman<br><a href="mailto:wasserman.louis@gmail.com">wasserman.louis@gmail.com</a><br>