„Insertion sort“ unter Hinzufügung eines Indexfeldes

insertion ( int a [ ] , int p [ ], int N )

{

int i, j, v ;

for ( i = 0 ; i <= N ; i ++ ) p [ i ] = i ;

for ( i = 2 ; i <= N ; i ++ )

{

v = p [ i ]; j = i ;

while ( a [ p [j - 1]] > a [ v ])

{ p [ j ] = p [j - 1] ; j-- ; }

}