Sortie

indice $k$ tel que

1. $k \in [g,d]$
2. $val < tbl[k]$
3. $\forall i \in [g,k[, tbl[i] \leq val$

Cette spécification exprime que Rang renvoie la position $k$ telle que tous les éléments situés avant cette position soient inférieurs ou égaux à val, et telle que l'élément à la position $k$ soit le premier plus grand que val.

Dans le cadre du tri par insertion, il faudra donc insérer $val$ sur l'indice $k$ et décaler les autres élements, notamment celui qui occupait l'indice $k$. Il s'agit bien de la position que devrait occuper $val$ dans le tableau trié.

Il existe plusieurs implémentations de l'algorithme Rang. Elles sont détaillées ci-après.