ordenação por comparação

Um algoritmo de comparação é um tipo de algoritmo de ordenação que lê apenas os elementos da lista através de uma operação de comparação abstrata única (muitas vezes um operador "menor ou igual a"), que determina qual dos dois elementos devem ocorrer em primeiro lugar na lista final de classificação. A única exigência é que o operador cumpra a duas das propriedades de uma ordem total: 1. * se a ≤ b e b ≤ c então a ≤ c (transitividade) 2. * para todo a e b, ou a ≤ b ou b ≤ a (totalidade ou tricotomia). É possível que que ocorra que tanto a ≤ b quanto b ≤ a; neste caso, tanto um quanto outro podem vir em primeiro lugar na lista de ordenação. Em uma ordenação estável, a ordem de entrada determina a ordem de classificação neste caso. Uma metáfora para pensar sobre o tipo de comparação é que alguém tenha um conjunto de pesos não rotulados e uma balança com escala. Seu objetivo é alinhar os pesos em ordem de seu peso, sem qualquer informação, exceto a obtida colocando-se dois pesos na balança e vendo qual deles é mais pesado (ou se ambos tem o mesmo peso).