You need to sort by start address. You're lucky that your input data was already sorted
No, I'm not. My original problem specification guaranteed
Anyway, those changes wouldn't slow down the program
so much that I'd prefer to use the code you posted above.
But you said the code above was an order of magnitude faster,
not an order of magnitude slower, so I wonder what's up?
Someone made a mistake, and I'm less than 50% confident that
it was you.