Shellsort
man sorgt dafür, daß Vertauschungen über größere Abstände möglich werden. Dazu wird abnehmende Folge von Inkrementen h t, ..., h1 definiert, so daß h1 = 1.
Eine Folge k1,..., kN heißt h-sortiert,
wenn für alle i, 1 ? i ? N-h, ki ? ki+h
Array a wird nun mit Einfügesort ht sortiert, dann ht-1 sortiert usw. bis a 1-sortiert und damit sortiert ist.