On Thu, Jul 16, 2009 at 07:48:33PM -0400, Louis Wasserman wrote:
* I completely rewrote the sorting method. The sort is unstable, but it is 40 lines (much more maintainable than the several-hundred line implementation from earlier) and runs *twice as fast as* (fromList . Data.List.sort . toList) for n=50000. (For sorted lists, it clocks in at about 4x faster.)
How does it compare against sortBy cmp xs = fromList2 (size xs) (Data.List.sortBy cmp (toList xs)) I'm inclined to agree with John that stability is important in a general purpose sort.
* partition is now in fact implemented via a simple foldl', which is actually faster than my old, several-dozen-line implementation as well as obviously simpler.
I had forgotten to mention that zipWith had been modified to a one-liner with mapAccumL, which actually proved faster than my implementation.
That is good news indeed.