Shell sort function

I wrote a Python sort function that uses shell sort:

# shell sort
# ignore the comments
def shell_sort(sequence):
    # shell sort needs an increment sequence
    # the increment sequence used here is 1, 2, 4, 8, 21, 56, 149, 404, 1098...
    # the sequence is defined by the following equation: round(e^(n-2)) + 1

    # initialize the increment_sequence
    increment_sequence = []
    e = 2.718281828459
    counter = 0
    while True:
        counter += 1
        current_value = int(round(e ** (counter - 2)) + 1)
        if current_value >= len(sequence): break
        increment_sequence.append(current_value)

    # loop through the increment sequence
    for i in increment_sequence:
        # loop through each subset of the sequence
        for j in xrange(i):
            # loop through each element in the subset
            for k in xrange(j, len(sequence), i):
                guess = k
                # find the correct place for the element
                while guess >= i and sequence[guess - i] > sequence[guess]:
                    sequence[guess], sequence[guess - i] = sequence[guess - i], sequence[guess]
                    guess -= i

    return sequence

The function uses a quadruple nested loop. I think that is overkill, and other (non-Python) code on the Internet only a double loop. On my computer, this is twice as slow as linear insertion. How can I reduce the number of loops?

Shell sort requires 3 loops because of the nature of the algorithm, you can get rid of one looping construct by making a recursive call but there's always loops+recursive calls >= 3. So I don't see how other code you have found uses only 2 loops. The main issue with precomputing the indexes that you are iterating over is that you start to negate one of the best benefits of shell sort, specifically if you do that you no longer have O(1) additional space used You will have fewer loops but you'll get some higher space complexity.
Syntactically you might be able to get less levels of indentation with some other approaches but it may not be more readable.

With that said there are a few changes I would make. I'd break out the increment generation into it's own function, taking your code mostly as-is this would become:

def generate_increments_sequence(length):
    """Generate the sequence of increments needed by shellsort
    for a sequence of the given length"""
    e = 2.718281828459
    increment_sequence = []
    counter = 0
    while True:
        counter += 1
        current_value = int(round(e ** (counter - 2)) + 1)
        if current_value >= length:
            break
        increment_sequence.append(current_value)
    return increment_sequence

Now it's worth noting that there's library function for exponentiation math.exp

import math
def generate_increments_sequence(length):
    """Generate the sequence of increments needed by shellsort
    for a sequence of the given length"""
    increment_sequence = []
    counter = 0
    while True:
        counter += 1
        current_value = int(round(math.exp(counter - 2)) + 1)
        if current_value >= length:
            break
        increment_sequence.append(current_value)
    return increment_sequence

You can then use thin in the original function as follows:

def shell_sort(sequence):
    """Sort a sequence using the shell sort algorithm
    :sequence: the sequence to be sorted
    """
    seq_len = len(sequence)
    increment_sequence = generate_increments_sequence(seq_len)

    for incr in increment_sequence:
        # loop through each subset of the sequence
        for j in xrange(incr):
            # loop through each element in the subset
            for k in xrange(j, seq_len, incr):
                guess = k
                # find the correct place for the element
                while guess >= incr and sequence[guess - incr] > sequence[guess]:
                    sequence[guess], sequence[guess - incr] = sequence[guess - incr], sequence[guess]
                    guess -= incr

    return sequence

The benefit of this is that it starts splitting out the increment generation from the sort generation, which is useful if you are to choose other increment strategies for your shell sort algorithm. If you find that you are calling the sort function a lot of times for the same sequence lengths you can then memoize the results for the generate_increments_sequence functions.

Making that change we get something like this:

def shell_sort(sequence, increment_function):
    """Sort a sequence using the shell sort algorithm
    :sequence: the sequence to be sorted
    :increment_function: function that generates the increment steps
    """
    seq_len = len(sequence)
    increment_sequence = increment_function(seq_len)

    for incr in increment_sequence:
        # loop through each subset of the sequence
        for j in xrange(incr):
            # loop through each element in the subset
            for k in xrange(j, seq_len, incr):
                guess = k
                # find the correct place for the element
                while guess >= incr and sequence[guess - incr] > sequence[guess]:
                    sequence[guess], sequence[guess - incr] = sequence[guess - incr], sequence[guess]
                    guess -= incr

    return sequence

which we can call with:

sorted_seq = shell_sort(foo, generate_increments_sequence)

StackExchange Code Review Q#101032, answer score: 5