[Haskell-beginners] sorting almost sorted list

[David Fletcher]

On Mon, 26 Sep 2011 19:46:29 -0700 Dennis Raddle wrote:

> I have a problem from music. I have a list of notes sorted by begin
> time. I want to sort them by end time.
>
> Notes that are sorted by begin time are usually close to sorted by end
> time, because notes tend to cluster within a small range of durations.
>
> What algorithms are available to me (hopefully in a library) that are
> good with this kind of thing?
>

How about something like this?  It keeps an output queue sorted by the end
time.  We allow notes to exit the queue and become part of the result as
soon as we can guarantee we aren't going to see any notes with an earlier
end time.


data Note = Note { begin :: Integer, end :: Integer }

noteSort :: [Note] -> [Note]
noteSort = noteSort' []

noteSort' :: [Note] -> [Note] -> [Note]
noteSort' outq [] = outq
noteSort' outq (x:xs) = out ++ noteSort' outq'' xs
           where (out, outq') = span (`entirelyBefore` x) outq
                 outq'' = insertBy (comparing end) x outq'

entirelyBefore :: Note -> Note -> Bool
a `entirelyBefore` b = end a < begin b


Here I've used a sorted list for the queue, so in the worst case (with a
note that lasts for the whole piece), it degrades into an insertion sort
of the whole thing.  But you could replace that list with a heap, and then
it would degrade into a heapsort.

David.