I personally liked how the examples seamed to start with worst-cast and progress toward their new possibly "best case" method.
What do you think is gained by starting with the new result?
Since the paper is about the new method, one assumes the examples show the new method's results. The first impression, is that the new method isn't very effective.
No, don't do that. The current order is fine. I want to see the algorithm's effect when compared to the old algorithm.