Animated Sorting Algorithm Demo: Shell Sort

Algorithm

h = 1
while h < n, h = 3*h + 1
while h > 0,
    h = h / 3
    for k = 1:h, insertion sort a[k:h:n]
    invariant: each h-sub-array is sorted
end
        

Properties

• Stable
• In place: O(1) extra space
• Worst case time: O(n^3/2) or better (see below)
• Adaptive: O(n·log₃(n)) when nearly sorted

Discussion

The worse-case time complexity of shell sort depends on the increment sequence. For the increments 1 4 13 40 121..., which is what is used here, the time complexity is O(n^3/2). For other increments, time complexity is known to be O(n^4/3) and even O(n·lg²(n)). Neither tight upper bounds on time complexity nor the best increment sequence are known.

Because shell sort is based on insertion sort, shell sort inherits insertion sort's adaptive properties. The adapation is not as dramatic because shell sort requires one pass through the data for each increment, but it is significant. For the increment sequence shown above, there are log₃(n) increments, so the time complexity for nearly sorted data is O(n·log₃(n)).

Because of its low overhead, relatively simple implementation, and adaptive properties, and because it is the only stable sub-quadratic sorting algorithm that uses O(1) extra space, shell sort is often a good alternative to the more advanced O(n·lg(n)) sorting algorithms.

Directions

• Click on to restart the animations.
• Click on a size number to change the size of the examples.
• Click on a cell to restart an individual animation.
• Click on a cell title to explore that input order.

Key

• Black values are sorted.
• Gray values are unsorted.
• Dark gray values show the current sub-array that is being sorted using insertion sort.
• A red triangle marks the algorithm position.

References

Algorithms in Java, Parts 1-4, 3rd edition by Robert Sedgewick. Addison Wesley, 2003.