Ein Sortierverfahren ist ein Algorithmus, der dazu dient, eine Folge von Elementen in eine sortierte Folge zu bringen. Voraussetzung ist, dass auf der Menge der Elemente eine strenge schwache Ordnung definiert ist, z.B. die lexikographische Ordnung von Zeichenketten oder die numerische Ordnung von Zahlen.
Man unterscheidet grundsätzlich zwischen allgemeinen vergleichsbasierten Sortierverfahren und speziellen nicht-vergleichsbasierten Sortierverfahren. Vergleichsbasierte Verfahren basieren auf paarweisen Vergleichen der zu sortierenden Elemente. Bei der Komplexitätsanalyse wird davon ausgegangen, dass der Aufwand zum Vergleich zweier Elemente konstant ist, sodass man mittels eines Entscheidungsbaumes beweisen kann, dass es eine untere Schranke Ω(n log n) für solche Verfahren gibt.
Die verschiedensten Sortierverfahren bieten unterschiedliche Vorteile, so dass sie je nach Zweck gezielt verwendet werden können. Man unterscheidet z.B. zwischen stabilen und instabilen Sortierverfahren. Stabile Sortierverfahren sind solche, die die relative Reihenfolge von Elementen, die bezüglich der Ordnung äquivalent sind, nicht verändern. Instabile Verfahren garantieren dies nicht.
Zudem unterscheidet man zwischen Sortierverfahren, die in-place (bzw. in-situ) arbeiten, d.h. die ohne oder nur mit einer konstanten kleinen Menge an zusätzlichen Speicherplatz arbeiten, und solchen, die dies nicht tun.
Unter bestimmten Rahmenbedingungen arbeiten manche Verfahren äußerst effizient, z.B. bei kleineren Datenmengen oder größtenteils bereits vorsortierten Daten.
