Tepifsort

Tepifsort gehört zur Gruppe der umhüllenden Sortieralgorithmen. Seine Laufzeit hängt maßgeblich vom intern verwendeten echten Sortierverfahren ab.

Tepifsort steht für das Sortieren mittels eines temporären Zeiger- oder Indexfeldes (temporary pointer/index field) und ist somit kein echtes Sortierverfahren. Vielmehr kann jedes existierende Sortierverfahren in eine Tepif-Variante umgesetzt werden, so daß die Schreibbelastung (Vertauschungen, Verschiebungen) auf ein Feld (oder Liste) von zu sortierenden Elementen minimal ausfällt (Θ(n)).

Dieses Verfahren ist immer zu bevorzugen, wenn Schreibbelastungen besonders teuer oder die Elemente besonders groß sind (z.B. Festplatten- oder Netzwerkzugriffen). Ein weiterer Vorteil ist, daß das Feld A während des gesamten Sortiervorganges keine Änderungen erfährt. Erst am Ende werden die Vertauschungen kompakt durchgeführt. Die Laufzeit ändert sich durch das Verfahren nicht wirklich, da Vertauschungen/Verschiebungen immernoch stattfinden (auf Feld B). Wir betrachtet aber nur Feld A.

Der Name "Tepifsort" kommt von tepif (eng. temporary pointer/index field, dt. temporäres Zeiger-/Indexfeld), da das Verfahren auf der Verwendung dieser Datenstruktur beruht.

Die Idee wurde erstmalig von Peter Weigel vorgestellt (Dezember 2000).