[Haskell-beginners] sorting almost sorted list

[Daniel Fischer]

On Tuesday 27 September 2011, 11:32:35, Yitzchak Gale wrote:
> 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?

I have to confess, I'm not even sure what you mean.
Okay, m is the maximal number of following notes that may end earlier than 
the current. But to which list(s) does the length refer?

> 
> test n k = fmap (all isSorted . map (sortAlmostBy n compare)) $ rands k

With what parameters did you call test?

Prelude Almost System.Random> test 12 16
True
(0.12 secs, 178509776 bytes)
Prelude Almost System.Random> test 12 17
False
(0.00 secs, 592904 bytes)

The only big variation in runtimes I find is due to a violation of the 
preconditions of sortAlmostBy, when all shortcuts.
(But the most of the runtime is used for generating the lists. If I 
completely evaluate such a list of lists prior to sorting, then m has a 
measurable impact on time even when all doesn't shortcut, however, in that 
situation it's basically monotonic in m, as expected).

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

You generate 100 lists of length 1000, such that the entries at index
k*d <= i < (k+1)*d are between k*d (inclusive) and (k+1)*d (exclusive).

Now, if you split those lists into chunks of length m, the preconditions of 
sortAlmostBy are only guaranteed to hold if each of the d-long chunks from 
the generation meets at most two m-long chunks.
That is the case if (and only if, if the entire list is long enough)

m + gcd m d >= d

If m + gcd m d < d, you will sooner or later encounter a d-chunk meeting 
three (or more) m-chunks. The probability that the first element of that 
d-chunk is larger than the last is nearly 1/2 [(d-1)/2d], so it doesn't 
take many such situations until you get a non-sorted list with 
sortAlmostBy m.

So, if running time is monotonic in m, under the assumption that the 
preconditions of sortAlmostBy hold, the optimal choice of m is

min { m \in N : m + gcd m d >= d }

For even d, that's d/2, for d prime it's d-1, generally, it's (1 - 1/p)*d, 
where p is the smallest prime factor of d.

I haven't analysed your merging function, but at first glance, merging c 
chunks of length m each is O(c*m); so, since sorting each chunk is 
O(m*log m), it'd overall be

O(c*m*log m) = O(n*log m) = O(n*log (n/c))

It has larger overhead than sortBy, so if n is small or m is large, sortBy 
is likely to be better, but if n is large and m relatively small, 
sortAlmostBy can be significantly (but not dramatically, excluding extreme 
cases where you can do much better) faster.