Anmerkung: wie läßt sich Grad der Vorsortierung einer Folge F = k1,...,kn von Schlüsseln messen?
Vorschlag 1: Zahl der Inversionen (Vertauschungen) von F
inv(F) = |{(i,j) | 1? i < j ? n, ki > kj}|
mißt so etwas wie Entfernungen zur richtigen Position
Vorschlag 2: Anzahl der runs, d.h. der vorsortierten Teillisten (siehe oben)
runs(F) = |{(i) | 1 ? i < n, ki+1 < ki}| + 1
Vorschlag 3: Länge der längsten sortierten Teilliste, las(F), bzw. rem(F) = n - las(F) (damit wie oben kleiner besser ist)