Sortiergeschwindigkeit
Das wichtigste allgemein in der Literatur genannte Merkmal des Sortierens ist die Sortierdauer („Laufzeit“, „Zeitkomplexität“) bzw. die Sortiergeschwindigkeit. Tendenziell, das ist sicher nicht verwunderlich, sortieren alle Sortieralgorithmen umso langsamer, je mehr Elemente sie zu sortieren haben. Auch bei den schnellsten auf Vergleiche beruhenden Algorithmen, den asymtotisch optimalen Sortieralgorithmen, wächst die Sortierdauer stärker als die Elementeanzahl x („leicht überlineares“ Wachstum: „x*log(x)“), im schlimmsten Falle wächst diese Dauer sogar hyperexponentiell („ xx “) mit der Elementeanzahl. Schneller, nämlich linear mit der Elementeanzahl ansteigend, sortieren nur noch die nicht auf Vergleichen beruhenden speziellen Sortieralgorithmen, die jedoch Einschränkungen haben .
Etliche Sortieralgorithmen sind so langsam, daß sie für ihren praktischen Einsatz, und sei es auch nur für eine überschaubare Elementeanzahl, deshalb nicht infragekommen.
Das Sortieren kann ggf. spürbar beschleunigt werden, wenn nicht die zu sortierenden Elemente selbst (im Speicher), sondern indirekt nur die sog. Zeiger bzw. Pointer, die auf ihre Speicheradressen zeigen, in die richtige Reihenfolge gebracht werden, jedoch ist der Aufruf, die Adressierung der Sortierelemente dann etwas aufwendiger, außerdem ist diese Programmierung wegen dieses „Adressierumweges“ leider deutlich fehleranfälliger. Während die zu sortierende Elementemenge auch nach dem Sortieren wegen des nur lesenden Zugriffs dieselbe Reihenfolge wie am Sortieranfang hat, haben die Zeiger nach dem Sortieren ihre Reihenfolge geändert: Der erste Zeiger zeigt auf das kleinste Sortierelement, der zweite auf das zweitkleinste usw. Auch das läßt sich mit einer Analogie plausibilisieren: Die Objekte verbleiben in ihren Fächern, jedoch hat man eine geordnete Liste (oder einen Kärtchenstapel): Der erste Listeneintrag (oder das erste Kärtchen) beinhaltet die Nummer des Faches mit dem kleinsten Element usw.
Die Sortiergeschwindigkeit hängt auch von der verwandten Datenstruktur ab. So sind Insertion- und Bubblesort gemeinhin langsam, auch und vor allem deshalb, weil sie i.d.R. Vektoren zu sortieren haben und dabei viele (eigentlich unnötige) Datenbewegungen verursachen. Läßt man diese Sortierverfahren jedoch auf Listen los, entfallen diese Datenbewegungen und werden von vergleichsweise wenigen Datenverknüpfungen ersetzt, die besagten Algorithmen mithin deutlich beschleunigt. Ein weiteres Optimierungspotential ist beim Insertionsort eine effizentere Suche (Intervallhalbierung) in der schon sortierten Teilmenge.
Die im Programm vorgenommene - grobe - Einteilung der Sortiergeschwindigkeit hat nicht zwangsläufig etwas mit der Komplexität zu tun. So wird z.B. Select(ion)sort als schnell beschrieben, was es mit den Elementezahlen, die Monitore mit ihren Auflösungen zu haben, auch ist, tatsächlich ist seine Komplexität jedoch quadratisch (begründet in dem überbordenden Suchen in der unsortierten Menge). Ab etlichen tausend Elementen wird es deshalb deutlich langsamer und fällt hinter andere zurück, mit denen es auf dem Bildschirm noch mithalten kann.