[DE] Shellsort Laufzeitanalyse
Donald Shell stellt 1959 in [📖She59] einen Sortieralgorithmus vor, der später nach ihm benannt wird: Shellsort.
Die in dem Algorithmus verwendete Sortiermethode ist auch bekannt als
Sortieren mit abnehmenden Inkrementen [📖OW17b, p. 88], das Verfahren ist eine Variation von Insertion Sort:
[Shellsort] uses insertion sort on periodic subarrays of the input to produce a faster sorting algorithm. [📖CL22, p. 48]
In der vorliegenden Implementierung (siehe Listing 1) werden Inkremente[^1] [^2] der Form verwendet, um -sortierte Folgen zu erzeugen. Im letzten Schritt sortiert der Algorithmus dann in die Schlüssel mit Abstand=.
Die Effizienz des Sortierverfahrens ist stark abhängig von : So zeigt Knuth, dass gilt, wenn für gilt: mit (vgl. [📖Knu97c, p. 91][^3]. In unserem Fall können wir von ausgehen.