Introduction

Shellsort’s performance depends heavily on the gap sequence you choose. There is no single universally optimal sequence for every machine and input distribution, so comparisons such as geometric gaps around 2.2 to 2.5 versus Tokuda’s sequence are mostly about empirical tradeoffs rather than one simple theorem. The practical question is which sequence gives fewer comparisons and moves on realistic arrays.

Why Gap Sequences Matter

Shellsort works by running insertion-sort-like passes over elements separated by a gap, then shrinking the gap until it reaches 1.

A simplified implementation:

1def shellsort(arr, gaps):
2    arr = arr[:]
3    for gap in gaps:
4        for i in range(gap, len(arr)):
5            temp = arr[i]
6            j = i
7            while j >= gap and arr[j - gap] > temp:
8                arr[j] = arr[j - gap]
9                j -= gap
10            arr[j] = temp
11    return arr

The gap sequence controls how much disorder is removed early and how much work remains for the final gap-1 pass.

The Geometric 2.48-Style Idea

A geometric sequence near 2.48 means successive gaps shrink by dividing by about 2.48. In practice, this produces a steadily decreasing progression with relatively simple generation.

A toy generator:

1import math
2
3
4def geometric_gaps(n, ratio=2.48):
5    gaps = []
6    gap = 1
7    while gap < n:
8        gaps.append(gap)
9        gap = max(gap + 1, int(math.floor(gap * ratio)))
10    return list(reversed(gaps[:-1])) + [1]
11
12
13print(geometric_gaps(100))

The details vary depending on how you round and where you start. The point is that the gaps come from a near-geometric progression.

These sequences are popular because they are easy to describe and often perform well empirically.

Tokuda’s Sequence

Tokuda proposed a specific empirically strong sequence that is often written in generated form and then truncated to the array size.

A common generator is:

1import math
2
3
4def tokuda_gaps(n):
5    gaps = []
6    k = 1
7    while True:
8        gap = int(math.ceil((9 * (9 / 4) ** (k - 1) - 4) / 5))
9        if gap > n:
10            break
11        gaps.append(gap)
12        k += 1
13
14    gaps.reverse()
15    if not gaps or gaps[-1] != 1:
16        gaps.append(1)
17    return gaps
18
19
20print(tokuda_gaps(100))

Tokuda’s sequence is one of the classic Shellsort choices because it repeatedly shows strong practical performance in experiments.

Which One Is Better

The honest answer is: usually Tokuda is a strong default, but the exact winner depends on implementation details, array sizes, and hardware effects.

In broad terms:

• Tokuda is widely regarded as a strong empirical sequence
• geometric sequences near 2.2 to 2.5 can also perform very well
• the differences are often in constant factors, not in changing Shellsort into a fundamentally different asymptotic algorithm

If you are choosing a general-purpose Shellsort variant without deep tuning, Tokuda is often the safer off-the-shelf answer because it has a strong practical reputation.

If you are benchmarking a particular workload, measure both on your input distribution rather than assuming one mathematical-looking formula must always win.

Benchmarking the Sequences

A simple timing harness helps compare them directly.

1import random
2import time
3
4
5def benchmark(sort_fn, gaps_fn, n=5000, trials=5):
6    total = 0.0
7    for _ in range(trials):
8        data = [random.randint(0, 100000) for _ in range(n)]
9        gaps = gaps_fn(n)
10        start = time.perf_counter()
11        sort_fn(data, gaps)
12        total += time.perf_counter() - start
13    return total / trials
14
15
16print("Tokuda:", benchmark(shellsort, tokuda_gaps))
17print("Geom:", benchmark(shellsort, geometric_gaps))

This kind of experiment is more useful than arguing from formulas alone because Shellsort performance is famously sensitive to gap design and constant factors.

What Theory Does and Does Not Tell You

Shellsort is a good example of an algorithm where theory and practice are both interesting but not perfectly aligned. Many gap sequences are motivated by empirical results, and exact worst-case bounds do not always predict which sequence is best on ordinary random or partially ordered arrays.

So if the question is “which should I use in code,” the answer is often empirical. If the question is “which has a prettier closed form,” that is a different discussion.

Common Pitfalls

The most common mistake is assuming a gap sequence with a nice mathematical formula must automatically outperform others on real hardware. Another is comparing sequences without fixing the rest of the implementation, because insertion-pass details and language overhead also matter. Developers also often benchmark on one tiny array size and overgeneralize the result. A final issue is forgetting that Shellsort itself is already a niche choice in many contexts where simpler library sorts or faster asymptotic algorithms are available.

Summary

• Shellsort performance depends strongly on the gap sequence.
• Geometric sequences near 2.48 can work well, but Tokuda is a strong practical default.
• The “best” sequence is usually an empirical question, not a universally settled theorem.
• Benchmark the sequences on the input sizes and distributions you actually care about.
• Tokuda’s sequence is widely respected because it consistently performs well in practice.