Ordenação estável

Um algoritmo de ordenação diz-se estável se preserva a ordem de registros de chaves iguais. Isto é, se tais registros aparecem na sequência ordenada na mesma ordem em que estão na sequência inicial.

Esta propriedade é útil apenas quando há dados associados às chaves de ordenação.

Um exemplo de um algoritmo de ordenação estável é o Counting Sort, que ordena um vector de valores inteiros (cujo valor máximo é conhecido) colocando cada valor na sua posição homónima num vector de comprimento igual ao valor máximo. Este algoritmo tem a particularidade de ser linear no tamanho do vector que será ordenado, já que prescinde de comparações entre valores.