Sammenligningsortering
En sammenligningsortering er en type sorteringsalgoritme som bare leser elementene gjennom en enkel abstrakt sammenligning (ofte «mindre enn eller lik» operatoren eller en treveis sammenligning) som bestemmer hvilke av to elementer som burde inntreffe først i den endelige sorterte listen. Det eneste kravet er at operatoren følger to av kritertene på total orden:
- Hvis a ≤ b og b ≤ c da er a ≤ c (transitivitet)
- For alle a og b, er enten a ≤ b eller b ≤ a (trikotomi)
Det er mulig at både a ≤ b og b ≤ a; i dette tilfelle kan hver av dem komme først i den sorterte listen. I en stabil sortering, bestemmer innmatningen den sorterte rekkefølgen I dette tilfellet.
En metafor på sammenligningsortering er at noen har plassert vekter på en vektstang. Målet er å sortere vektene etter vekt uten noen annen informasjon enn hva vektstangen forteller er tyngre eller har samme vekt.