I wrote:
Can you guarantee for some value of m that for each note N, only the first m notes following N might end earlier than N? If so, then the following simple algorithm is linear and runs in constant space. You could then use: sortAlmostBy m (comparing endTime) ...You might be able to do a little better than this.
After running some tests, it seems empirically that you can use m `div` 2 instead of m for lists of even length, which gives you a nice speedup for larger values of m. For lists of prime length, the best you can do seems to be m-1. It's more complicated for lists of non-prime odd length. I can't immediately see why any of that is true. Daniel to the rescue perhaps? test n k = fmap (all isSorted . map (sortAlmostBy n compare)) $ rands k isSorted xs = and . zipWith (<=) xs $ drop 1 xs rands d = fmap (take 100 . map (concat . zipWith (map . (+)) [0,d ..] . chunksOf d) . chunksOf 1000 . randomRs (0, d-1)) newStdGen Thanks, Yitz