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:

Times (ms)
                 min      mean    +/-sd    median    max
to/from list: 106.742 111.269    4.831 110.207 138.638
pairing heap:   62.896   66.066    2.410   65.433   74.471
stable pheap:   95.600 102.381    5.807 100.744 120.395

Even worse, the stable heapsort becomes genuinely worse when there's memory to spare; with +RTS -H128m:

Times (ms)
                 min      mean    +/-sd    median    max
to/from list:   53.675   84.407   14.130   86.319 108.553
pairing heap:   62.492   77.065    9.649   78.883 104.606
stable pheap:   70.437   97.718   15.332 100.548 134.624

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.)

I had forgotten to mention that zipWith had been modified to a one-liner with mapAccumL, which actually proved faster than my implementation.

Louis Wasserman
wasserman.louis@gmail.com