[laszlokorte]

Actually I would assume the time for removing each rod while collecting the result is quadratic because when the number of rods is high enough you can no longer see the highest one at a glance but have to scan through all possible rod positions for spotting the one that sticks out.

[ladberg]

In spaghetti sort I think you place your hand at the top and remove the first piece to touch it. That takes it from O(n) to O(1) to remove a single piece.

Of course, your hand is then a magical device that can do a reduction in constant time.