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 sortedend

- Not stable
- O(1) extra space
- O(n
^{3/2}) time as shown (see below) - Adaptive: O(n·lg(n)) time when nearly sorted

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^{2}(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_{3}(n) increments, so the time complexity
for nearly sorted data is O(n·log_{3}(n)).

Because of its low overhead, relatively simple implementation, adaptive properties, and sub-quadratic time complexity, shell sort may be a viable alternative to the O(n·lg(n)) sorting algorithms for some applications when the data to be sorted is not very large.

- Click on above to restart the animations in a row, a column, or the entire table.
- Click directly on an animation image to start or restart it.
- Click on a problem size number to reset all animations.

- 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.

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

*Programming Pearls*
by Jon Bentley.
Addison Wesley, 1986.

*Quicksort is Optimal*
by Robert Sedgewick
and Jon Bentley,
Knuthfest, Stanford University, January, 2002.

Dual Pivot Quicksort: Code and Discussion.

*Bubble-sort with Hungarian ("Csángó") folk dance * YouTube video, created at Sapientia University, Tirgu Mures (Marosvásárhely), Romania.

*Select-sort with Gypsy folk dance * YouTube video, created at Sapientia University, Tirgu Mures (Marosvásárhely), Romania.

Sorting Out Sorting, Ronald M. Baecker with the assistance of David Sherman, 30 minute color sound film, Dynamic Graphics Project, University of Toronto, 1981. Excerpted and reprinted in SIGGRAPH Video Review 7, 1983. Distributed by Morgan Kaufmann, Publishers. Excerpt.