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:

• a[0...n - 1] ist Permutation von A[0...n - 1]
• a₀$\le$...a_k und a_k+1$\le$...$\le$a_i