Algorithm

The main idea behind the algorithm is that starting anywhere, taking the h-th entry yields a sorted subsequence. We will implement an algorithm that takes values for h from the sequence (1/2)(3^k - 1). This gives us the sequence 1,4,13,40… that will be called the increment sequence.

def shell(a):
    """
    Implements the shell sort algorithm. It is a variant of the insertion algorithm.
    """

    # Compute the increment sequence
    h = 1
    while h < (len(a) / 3):
        h = 3*h + 1

    # Sort
    while h >= 1:
        for i in range(h, len(a)):
            j = i
            while j >= h:
                if a[j] < a[j-h]:
                    temp = a[j]
                    a[j] = a[j-h]
                    a[j-h] = temp
                j = j-h
        h = h/3
    return a

Step by step

array = [1,0,3,4,2,5]

h = 1
len(array) = 6
h = 1 | h < 2 | True
h = 4 | h < 2 | False

h = 4
i = 4
    j = 4
        a[4] < a[4-4] | a[4] < a[0] | 2 < 0 | False
    j = 0

i = 5
    j = 5
        a [5] < a[5-4] | a[5] < a[1] | 5 < 1 | False
    j = 1

array = [1,0,3,4,2,5]

h = 1
i = 1
    j = 1
        a[1] < a[1-1] | a[1] < a[0] | 0 < 1 | True
        a[1] = 0
        a[0] = 1
        array = [0,1,3,4,2,5]
    j = 0

i = 2
    j = 2
        a[2] < a[2-1] | a[2] < a[1] | 3 < 1 | False
    j = 1
        a[1] < a[1-1] | a[1] < a[0] | 1 < 0 | False
    j = 0

i = 3
    j = 3
        a[3] < a[3-1] | a[3] < a[2] | 4 < 3 | False
    j = 2
        a[2] < a[2-1] | a[2] < a[1] | 3 < 1 | False
    j = 1
        a[1] < a[1-1] | a[1] < a[0] | 1 < 0 | False
    j = 0

i = 4
    j = 4
        a[4] < a[4-1] | 2 < 4 | True
            a[3] = 2
            a[4] = 4
            array = [0,1,3,2,4,5]
    j = 3
        a[3] < a[3-1] | 2 < 3 | True
            a[2] = 2
            a[3] = 3
            array = [0,1,2,3,4,5]
    j = 2
        a[2] < a[2-1] | 2 < 1 | False
    j = 1
        a[1] < a[1-1] | 1 < 0 | False
    j = 0

i = 5
    j = 5
        ... | False
    j = 4
        ... | False
    j = 3
        ... | False
    j = 2
        ... | False
    j = 1
        ... | False
    j = 0

h = 0
array = [0,1,2,3,4,5]

Complexity analysis

Time

O(N) = N^(3/2)

Space

We use the same array that is passed as argument and a few more variables, so the cost is: O(N) = N + K ≈ N.

Use cases

  • Large arrays
  • Arrays that are in arbitrary order