Verfahren

Die zu sortierenden Elemente werden nacheinander in einem B-Baum untergebracht. Diese Hilfstruktur wird dannach wieder aufgelöst und die Elemente direkt sortiert. D.h. die Vergleichs- und Vertauschungesoperationen sind zeitlich vollständig getrennt.

Das Prinzip ist das gleiche, wie bei Avlsort. Es wird lediglich intern die Datenstruktur eines B-Baumes statt eines AVL-Baumes verwendet. Die Einfügeoperation wird entsprechend ersetzt.

Aufgrund des Einfügens von Elementen in eine sortierte Menge wird dieses Verfahren auch als "Sortierung durch Einfügen" bezeichnet.