[Haskell-beginners] sorting almost sorted list

[Dennis Raddle]

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?

Dennis