Wenn das:
1 2 3 4 5 6 7 8 9
und das:
9 8 7 6 5 4 3 2 1
zu einer Worst-Case-Laufzeit führt, sollte das:
2 1 3 4 5 6 7 8 9
und das:
8 9 7 6 5 4 3 2 1
doch auch ein Worst-Case Verhalten provozieren, oder?
Edit: Oder eine dieser Folgen:
2 3 4 5 6 7 8 9 1
8 7 6 5 4 3 2 1 9
5 4 6 3 7 2 8 1 9
Ist doch gar nicht so schwer
Die Bedingung ist ja im Grunde, dass bei
einer beliebigen jeder Zahl alle Zahlen links davon entweder alle größer oder alle kleiner sind
