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.