Empirically Improved Tokuda Gap Sequence in Shellsort

12/21/2021

∙

by   Ying Wai Lee, et al.

∙

0

∙

share

Experiments are conducted to improve Tokuda (1992) gap sequence in Shellsort into γ-sequences, and the best result is the gap sequence in which the k-th increment h_k is given by h_k=⌈γ^k-1/γ-1⌉ , where γ=2.243609061420001... and k∈ℕ_1. The first few increments of the gap sequence are 1, 4, 9, 20, 45, 102, 230, 516, 1158, 2599, 5831, 13082, 29351, 65853, 147748, 331490, 743735, ... It empirically yields less numbers of comparison on average than Tokuda (1992) gap sequence. In the procedure of search, it reveals the potential existence of a new type of fractal.