Python でシェルソートを実装します。
シェルソート
シェルソート（改良挿入ソート、英語: Shellsort, Shell sort, Shell’s method）は、in-placeな比較ソートのアルゴリズムの一種である。シェルソートは、交換によるソート（バブルソート）あるいは挿入によるソート（挿入ソート）の一般化と見なすことができる[2]。ソートの方法は、まず、間隔の離れた要素の組に対してソートを行い、だんだんと比較する要素間の間隔を小さくしながらソートを繰り返す、というものである。離れた場所の要素からソートを始めることで、単純に近くの要素を比較する場合よりも速く、要素を所定の位置に移動させることができる。ただし、安定ソートではない。
出典: フリー百科事典『ウィキペディア（Wikipedia）』
ちょっとイメージしずらかったのですが、以下の動画で感覚がつかめました。
間隔をいくつにするかにより、シェルソートの性能は変わるそうです。
import random
def shell_sort(array):
gaps = [7, 3, 1]
for gap in gaps:
gap_insertion_sort(array, gap)
print(f'ギャップ {gap} ソート: {array}')
def gap_insertion_sort(array, gap):
for i in range(0, len(array), gap):
current_value = array[i]
position = i
while position >= gap and array[position - gap] > current_value:
array[position] = array[position - gap]
position = position - gap
array[position] = current_value
if __name__ == '__main__':
random.seed(1)
array = [random.randrange(100) for i in range(20)]
print('未ソート', array)
# 未ソート [17, 72, 97, 8, 32, 15, 63, 97, 57, 60, 83, 48, 26, 12, 62, 3, 49, 55, 77, 97]
shell_sort(array)
print('ソート済み', array)
# ギャップ 7 ソート: [17, 72, 97, 8, 32, 15, 63, 62, 57, 60, 83, 48, 26, 12, 97, 3, 49, 55, 77, 97]
# ギャップ 3 ソート: [3, 72, 97, 8, 32, 15, 17, 62, 57, 26, 83, 48, 60, 12, 97, 63, 49, 55, 77, 97]
# ギャップ 1 ソート: [3, 8, 12, 15, 17, 26, 32, 48, 49, 55, 57, 60, 62, 63, 72, 77, 83, 97, 97, 97]
# ソート済み [3, 8, 12, 15, 17, 26, 32, 48, 49, 55, 57, 60, 62, 63, 72, 77, 83, 97, 97, 97]
想定通りの結果を得ることができました。