procedure partitionner( ref int A[*], int inf, int sup, res int posPivot )
# PRECONDITION
#    inf < sup
# POSTCONDITION
#    A est une permutation de A',
#    inf <= posPivot <= sup,
#    A[posPivot] = A'[inf],
#    ALL( inf <= i <= posPivot :: A[i] <= A[posPivot] ),
#    ALL( posPivot <= i <= sup :: A[posPivot] <= A[i] )
{
  posPivot = inf;
  int pivot = A[posPivot];
  for [i = inf+1 to sup] {
    if (A[i] <= pivot) {
      posPivot += 1;
      A[i] :=: A[posPivot];    # Interchange les deux elements.
    }
  }

  # On deplace le pivot a sa bonne position.
  A[posPivot] :=: A[inf];    # Interchange les deux elements.
}

procedure trierRec( ref int A[*], int inf, int sup )
{
  if (inf >= sup) {
    # Tableau de taille 1: rien a faire
  } else {
    int posPivot;
    partitionner( A, inf, sup, posPivot ); # On partitionne a en deux parties.
    trierRec( A, inf, posPivot-1 );    # On effectue le tri de la partie gauche.
    trierRec( A, posPivot+1, sup );    # Idem pour la partie droite.
  }
}

procedure trier( ref int A[*], int n )
{
  trierRec( A, 1, n );
}