Lineares Einfügen

füge a[i] in a[0 .. i-1] ein = {
  Zahl k := i - 1;
  für (Zahl k von i-1 herab bis 0) {
     if ( a[k] <= a[k+1]) { 
        verlasse Schleife; 
     }
     tausche (a[k], a[k+1]);
  }
}

Invariante:



Johannes Waldmann 2009-01-12