(Shell Sorting) Applying Ciura's gap sequence (or some other optimal sequence formula)

Question

I've been trying to teach myself various sort methods just for the sake of being able to use them in the future and right now I've been teaching myself about shell sorts. I understand the way shell sorts themselves work (they're in essence insertions sorts except it only occurs between gaps that progressively decreases in size, allowing items to be moved across "larger distances"). One thing that I've heard about this algorithm is that you do have freedom over how you choose your gap sequence, since apparently if you choose a bad one it can make the sequence less efficient than even normal insertion sort. This is how I got to introduced to Ciura's gap sequence (1, 4, 10, 23, 57, 132, 301, 701 etc if I'm not mistaken) and Sedgewick's gap sequence formula which I think is 4*9^i-9*2^i+1.

The part where my confusion begins is trying to use these in context to a shell sorting method. Just as an example I've been looking at a simple function for a shell sort written in Java by GeeksForGeeks.

public static void shellSort(int[] arr) {
   int n = arr.length;

   for (int gap = n / 2; gap > 0; gap /= 2) {

     for (int i = gap; i < n; i++) {
                
     int temp = arr[i]; 
     int j = i;

     while (j >= gap && arr[j - gap] > temp) {
       arr[j] = arr[j - gap];
       j -= gap;
     }

     arr[j] = temp;
   }
}

I've spent about an hour or so trying to think about how this method could be refactored to use either Sedgewick's formula or Ciura's, but I've been stumped on this. For context I should say that the way I've been teaching myself these sort algorithms is by learning what the algorithm is both conceptually and from a basic code logic sense and then writing simple (but still fitting/functional) versions of them in Java so that I have a reference for applying them in other languages (since Java was the first language I learned). For example one problem that I've been thinking over is how 'large' the sequence should be. Should the first/highest gap value be equivalent to the array/structure's size or something else? Should the gap values then be stored in their own array to be referenced against the parameter, or should the for loop be able to handle that for me if I write it correctly?

I really wish I could crunch this question down into a TLDR, but I can't think of a good one as I've opted to lay out as much context to this as I could think of. Hopefully you can forgive me for that.

"it only occurs between gaps that progressively grow in size, such that items can moved across "larger distances")": the gaps decrease in size. — trincot
– trincot, Commented Nov 19 at 21:44

Yaksh · Accepted Answer · 2025-11-19 22:59:51Z

1

Shell sort works the same no matter what gaps you use.
The only thing that changes is which gaps you make between elements.
Think of it like this:
- Shell sort = “insertion sort, but you start by jumping far.”
- The gap sequence = “how big your jumps are before you switch to smaller jumps.”

Your code uses:
n/2 → n/4 → n/8 →... → 1

Ciura or Sedgewick just replace those numbers with better jump sizes.
So instead of letting Java calculate them in a loop, you simply:

Make a list of gaps (Ciura: 701, 301, 132 … 1)
Start from the biggest one that fits your array
Run the same sorting logic for each gap

Nothing else changes.
You are not rewriting the algorithm. you are only changing the list of gap numbers. That is all.
In other words: Shell sort = same engine, different gear ratios.

answered Nov 19 at 22:59

Yaksh

704 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Neptunium-Eater Nov 20 at 1:08

So it's overall not possible or not good practice to write the gap sequence as a math expression inside the iterator?

Yaksh Nov 20 at 1:29

Think of shell sort like climbing down stairs: You want good step sizes so you reach the bottom fast. You can try to make step sizes with a math formula on the spot. But the best step sizes have already been measured, so people keep them in a list. Using the list is faster, safer, and simpler than inventing steps every time. So: Possible? Yes. Good practice? Usually no. Most developers just store the gap list in an array and loop over it.

trincot · Accepted Answer · 2025-11-20 18:15:33Z

One idea could be to provide a stream of increasing gaps as second argument to the shellSort function. Then the caller can choose which gap sequence to provide. The sort function will then consume as many gaps as are needed for the given array, reverse that list of gaps, and then do the loop as you had it.

    // Shell sort now takes a gap sequence as second argument
    public static void shellSort(int[] arr, Stream<Integer> gapSequence) {
        int n = arr.length;
        // Collect gaps <= n
        List<Integer> gaps = gapSequence
                                .takeWhile(g -> g < n)
                                .collect(Collectors.toList());

        // Iterate gaps in reverse order
        Collections.reverse(gaps);

        for (int gap : gaps) {
            for (int i = gap; i < n; i++) {
                int temp = arr[i];
                int j = i;
                while (j >= gap && arr[j - gap] > temp) {
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                arr[j] = temp;
            }
        }
    }

    // Example gap sequence: this is Sedgewick, 1986, sequence https://oeis.org/A033622
    public static Stream<Integer> sedgewickSequence() {
        return Stream.iterate(0, i -> i + 1)
                     .map(i -> 1 + 
                         ((9 - i % 2) << i) - (((3 - i % 2) * 3) << ((i + 1) / 2))
                     );
    }
    
    public static void main(String[] args) {
        int[] arr = {23, 12, 1, 8, 34, 54, 2, 3, 18, 22, 6, 36, 7, 0, 27, 30, 11, 19, 14, 9};

        shellSort(arr, sedgewickSequence());

        System.out.println(Arrays.toString(arr));
    }

For Ciura's gap sequence there is no known formula as it was experimentally derived. But you could still create an infinite stream that starts with the known Ciura values, and then continues with some chosen formula when larger gaps are needed:

    public static Stream<Integer> ciuraSequence() {
        return Stream.concat(Stream.of(1, 4, 10, 23, 57, 132, 301, 701, 1750), // Ciura -- empirical
                             Stream.iterate(1750, g -> (int)(g * 2.25)));      // ...continuation after known gaps
    }

Here is the same with generators in other languages:

JavaScript

// Helper function
function* takeWhile(iter, predicate) {
    for (const value of iter) {
        if (!predicate(value)) break;
        yield value;
    }
}

// Shell sort now takes a gap sequence as second argument
function shellSort(arr, gapSequence) {
    const n = arr.length;
    // Collect gaps <= n
    const gaps = [...takeWhile(gapSequence, g => g < n)];

    // Iterate gaps in reverse order
    gaps.reverse();

    for (const gap of gaps) {
        for (let i = gap; i < n; i++) {
            const temp = arr[i];
            let j = i;
            while (j >= gap && arr[j - gap] > temp) {
                arr[j] = arr[j - gap];
                j -= gap;
            }
            arr[j] = temp;
        }
    }
}

// Example gap sequence: this is Sedgewick, 1986, sequence https://oeis.org/A033622
function* sedgewickSequence() {
    for (let i = 0; true; i++) {
        yield 1 + ((9 - i % 2) << i) - (((3 - i % 2) * 3) << ((i + 1) / 2));
    }
}

// main
const arr = [23, 12, 1, 8, 34, 54, 2, 3, 18, 22, 6, 36, 7, 0, 27, 30, 11, 19, 14, 9];

shellSort(arr, sedgewickSequence());

console.log(...arr);

Python

from itertools import takewhile, count

# Shell sort now takes a gap sequence as second argument
def shell_sort(lst, gap_sequence):
    n = len(lst)
    # Collect gaps <= n
    gaps = list(takewhile(lambda g: g < n, gap_sequence))

    # Iterate gaps in reverse order
    gaps.reverse()

    for gap in gaps:
        for i in range(gap, n):
            temp = lst[i]
            for j in range(i, gap-1, -gap):
                if lst[j - gap] <= temp:
                    break
                lst[j], lst[j - gap] = lst[j - gap], temp

# Example gap sequence: this is Sedgewick, 1986, sequence https://oeis.org/A033622
def sedgewick_sequence():
    for i in count(0):
        yield 1 + ((9 - i % 2) << i) - (((3 - i % 2) * 3) << ((i + 1) // 2))

# main
lst = [23, 12, 1, 8, 34, 54, 2, 3, 18, 22, 6, 36, 7, 0, 27, 30, 11, 19, 14, 9]

shell_sort(lst, sedgewick_sequence())

print(*lst)

This is a very interesting design that I'll have to try when I can (I say mainly because I'm not super familiar with Streams). Since I type out, analyze, and store these sample methods on Java for the purpose of giving myself the right mental framework in terms of figuring out these algorithms on other programming languages, I wonder if there's a way to replicate this kind of logic on other languages (the main ones I'm learning are C#, Python, and JavaScript). I'm sure there's a way of going about it, though as you can tell I haven't used streams a lot.
Since Java 16, you can directly use .toList() instead of .collect(Collectors.toList()).

Collectives™ on Stack Overflow

(Shell Sorting) Applying Ciura's gap sequence (or some other optimal sequence formula)

2 Answers 2

2 Comments

JavaScript

Python

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

JavaScript

Python

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related