[Haskell-beginners] sorting almost sorted list

[Yitzchak Gale]

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