Lineares Einfügen

Dieses einfachste aller Sortierverfahren nimmt beginnend bei I=2 das I-te Datenelement und fügt es an der entsprechenden Stelle im Datenfeld ein. Danach wird I um 1 erhöht und solange fortgefahren, bis alle Datenelemente bearbeitet sind. Sind nur wenige Daten zu sortieren, hat auch dies einfache Verfahren durchaus seine Berechtigung. Der Algorithmus lautet also: 
FOR I := 2 TO N DO
    (* füge den Wert von D[I] an entsprechender Stelle in D[1]...D[I] ein *)
Das Einfügen geschieht, indem für J von I-1 ausgehend das Element D[I] mit dem Element D[J] verglichen wird und dann entweder D[I] eingefügt oder D[J] nach rechts verschoben wird. Also muss das Element D[I] vorher auf einer Hilfsvariablen gespeichert werden.

Binäres Einfügen

Der vorhergehende Algorithmus lässt sich verbessern, indem die bereits vorhandene Ordnung der Elemente D[1] bis D[I] ausgenützt wird, um die Einfügungsstelle zu finden. Beim binären Einfügen wird in der Mitte der Elemente D[1] bis D[I] geprüft, ob H in der unteren oder in der oberen Hälfte eingefügt werden muss. Die entsprechende Teilfolge wird wieder halbiert, bis durch die Teilung die Einfügungsstelle gefunden worden ist.

Leider ergibt sich nur eine Reduzierung in der Zahl der Vergleiche, denn der Rest des Programms, also auch die Zahl der Verschiebungen, ist der gleiche wie bei der linearen Sortierung.

Bubblesort

Bei diesen beiden Verfahren wird wie bei den vorhergehenden das Feld mehrfach durchlaufen. Anstelle des Einfügens des entsprechenden Feldelements an der richtigen Stelle wird hier das jeweils kleinste Element durch Austausch mit dem Nachbarn an die passende Stelle gebracht. Wenn man das Feld vertikal aufschreibt, "perlt" das Feldelement nach oben an seinen Platz, und das hat diesem Verfahren den Namen eingetragen. In der Pascal-Version wird der Austausch durch die Prozedur SWAP erledigt.

Shakersort

Wenn man den Algorithmus auf die Möglichkeit der Verbesserung hin untersucht, fällt einem sicher gleich die feste Schleifenstruktur auf, die keine Rücksicht auf schon sortierte Sequenzen nimmt. Die erste Verbesserung ist dadurch möglich, wenn das Programm abbricht, wenn das Feld sortiert ist. Das ist der Fall, wenn in einem Durchlauf für I kein Austausch erfolgte. Weiterhin ist Bubblesort höchst asymmetrisch, wenn man zum Beispiel die beiden folgenden Felder betrachtet, kann man feststellen, dass D1 schon nach einem Durchlauf, D2 dagegen erst nach sieben Durchläufen sortiert ist. 
D1: 10 25 36 54 87  2
D2: 87  2 10 25 36 54
Die Asymmetrie lässt sich beseitigen, indem in aufeinanderfolgenden Durchläufen jeweils in entgegengesetzter Richtung gearbeitet wird. Dieses "Auf" und "Ab" hat dem Verfahren auch zu dem Namen Shakersort verholfen. Eine letzte Verbesserung ergibt sich, wenn man den Index festhält, bis zu dem das Feld schon sortiert ist.

Heapsort

Die bisher behandelten Algorithmen suchten immer nur ein Element, das kleinste aus der Restmenge von N-1 Elementen heraus. Die Sortiermethode lässt sich also nur beschleunigen, indem bei einem Durchlauf mehr Information gesammelt wird. Eine Sortiermethode, die nach diesem Schema verfährt, ist das Sortieren mit Bäumen. Dabei wird als Baum die unten gezeigte Anordnung der Elemente einer Datenmenge bezeichnet. Betrachten Sie dazu die Folge von Schlüsseln: 
40 50 10 45 90 15  5 65
Ordnet man diese Elemente in einem Baum derart, dass immer das kleinere Element als Wurzel verwendet wird, benötigt man N-1 Vergleiche. Wenn ein solcher binärer (= zweiästiger) Baum in einem linearen Feld gespeichert werden soll, ergibt sich die Bedingung: 
d [i] <= d [2i] und d [i]  <= d [2i+1]
(Die Feldkomponenten stehen unter den Schlüsseln.) Eine derartige Anordnung der Schlüssel heißt HEAP.

Quicksort

Diese schnellste aller Sortiermethoden wurde von C. A. Hoare entwickelt. Der Vorteil von Quicksort offenbart sich aber erst bei größeren Datenmengen. Bei diesem Algorithmus wird der Austausch von falsch postierten Elementen über größere Distanzen durchgeführt. Das Verfahren arbeitet folgendermaßen: