Eine Verbesserung von Quicksort ergibt sich aus der Beobachtung, daß ein rekursives Programm stets sich selbst für viele kleine Teildateien aufruft, daher sollte es eine möglichst gute Methode verwenden, wenn es kleine Teildateien verarbeitet. Ein offensichtlich möglicher Weg, um das zu erreichen, besteht darin, den Test zu Beginn des rekursiven Programms in der Weise abzuändern, daß Insertion Sort aufgerufen wird. Wenn der Insertion Sort aufgerufen wird, in einer Größenordnung zwischen 5 und 25, so läuft der Algorithmus ungefähr mit gleicher Effizienz ab. Die Verkürzung der Laufzeit liegt für die meisten Anwendungen in der Größenordnung von 20%.
|