Revision 18718041 of "Shell sort" on enwiki

'''Shell sort''' (or '''Shellsort''') is one of the oldest [[sorting algorithm|sorting algorithms]]. It was invented in 1959 by [[D. L. Shell|Donald L. Shell]] <nowiki>[</nowiki>[[#References|Sh]]<nowiki>]</nowiki>.
It is fast, easy to understand and easy to implement. 
However, its complexity analysis is a little more sophisticated.  
It is easy to develop an intuitive sense of how this algorithm works, but often difficult to analyze its execution time.

Shell sort is sometimes called "Shell-Metzner sort" after [[Marlene Metzner]] who wrote a very early implementation of Shell sort in [[FORTRAN]].  It was first called Shell-Metzner in an article in ''Creative Computing'' in [[1976]], but Marlene Metzner has said that her name should never have been attached to it.

== Basic concept ==

Shell sort is an extension of [[insertion sort]], with two observations in mind: 
#Insertion sort is efficient if the input is almost sorted. 
#Insertion sort is inefficient, on average, because it moves values just one position at a time. 

Shell sort is similar to insertion sort, but it works by taking bigger steps as it rearranges values, gradually decreasing the step size down towards one. 
In the end, Shell sort performs a regular insertion sort, but by then, the array of data is guaranteed to be almost sorted. 

Consider a small value that is initially stored in the wrong end of the array. Using insertion sort, it will take roughly ''n'' comparisons and exchanges to move this value all the way to the other end of the array. With Shell sort, we'll first move values using giant step sizes, so a small value will move a long way towards its final position, with just a few comparisons and exchanges.

The idea of Shell sort can be illustrated in the following way:
*  arrange the data sequence in a two-dimensional array 
*  sort the columns of the array 

The effect is that the data sequence is partially sorted. The process above is repeated, but each time with a narrower array, i.e. with a smaller number of columns. In the last step, the array consists of only one column. 
In each step, the sortedness of the sequence is increased, until in the last step it is completely sorted. However, the number of sorting operations necessary in each step is limited, due to the presortedness of the sequence obtained in the preceding steps.

== Example ==

Let

 3 7 9 0 5 1 6 8 4 2 0 6 1 5 7 3 4 9 8 2

be the data sequence to be sorted. First, it is arranged in an array with 7 columns (left), then the columns are sorted individually (right), with the largest element of each column at the bottom:
 3 7 9 0 5 1 6          3 3 2 0 5 1 5
 8 4 2 0 6 1 5    ->    7 4 4 0 6 1 6
 7 3 4 9 8 2            8 7 9 9 8 2
Data elements 8 and 9 have now already come to the end of the sequence, but a small element (2) is also still there. In the next step, the sequence is arranged in 3 columns, which are again sorted:
 3 3 2          0 0 1
 0 5 1          1 2 2
 5 7 4          3 3 4
 4 0 6    ->    4 5 6
 1 6 8          5 6 8
 7 9 9          7 7 9
 8 2            8 9
Now the sequence is almost completely sorted. When arranging it in one column in the last step, it is only a 6, an 8 and a 9 that have to move a little bit to their correct position.

In reality, the data sequence is not arranged in a two-dimensional array, but held in a one-dimensional array that is indexed appropriately. For instance, data elements at positions 0, 5, 10, 15, etc. would form the first column of an array with 5 columns. The "columns" obtained by indexing in this way are sorted with [[Insertion sort]], since this method has a good performance with presorted sequences.

== Analysis ==

The correctness of the algorithm follows from the fact that in the last step (with ''h'' = 1) an ordinary insertion sort is performed on the whole array. 
But since data are presorted by the preceding steps (''h'' = 3, 7, 31, ...), only a few insertion sort steps are sufficient. 
The exact number depends on the sequence of ''h'' values (denoted as ''h''-sequence). The ''h''-sequence above is just one of several possible.

* ([[Vaughan Pratt|Pratt]]) With the ''h''-sequence 1, 2, 3, 4, 6, 8, 9, 12, 16, ..., 2<sup>''p''</sup>3<sup>''q''</sup>, ... Shellsort needs O(''n''·log(''n'')<sup>2</sup>) steps for sorting a sequence of length ''n''.

* ([[Thomas Hibbard|Hibbard]]) With the ''h''-sequence 1, 3, 7, 15, 31, 63, 127, ..., 2<sup>''k''</sup> - 1, ... Shellsort needs O(''n''<sup>3/2</sup>) steps for sorting a sequence of length ''n'', in the worst case.  ''Empirically'' the ''average'' case seems to be O(''n''<sup>5/4</sup>).

* ([[Donald Knuth|Knuth]]) With the ''h''-sequence 1, 4, 13, 40, 121, ..., 3''h''<sub>''s''-1</sub> + 1 = (3<sup>''s''</sup> - 1)/2, ... ([[On-Line Encyclopedia of Integer Sequences|OEIS]] sequence [http://www.research.att.com/projects/OEIS?Anum=A003462 A003462])  Shellsort needs O(''n''<sup>3/2</sup>) steps for sorting a sequence of length ''n''. 

* ([[Robert Sedgewick|Sedgewick]]) With the ''h''-sequence 1, 5, 19, 41, 109, 209, ... (described below), ([[On-Line Encyclopedia of Integer Sequences|OEIS]] sequence [http://www.research.att.com/projects/OEIS?Anum=A033622 A033622])  Shellsort needs O(''n''<sup>4/3</sup>) steps for sorting a sequence of length ''n'', in the worst case.  ''Empirically'' the ''average'' case seems to be O(''n''<sup>7/6</sup>) – a very good asymptotic average performance.  Knuth recommends this choice, except perhaps for small values of ''n''.  

:<math>
  h_s=
  \left\{
   \begin{matrix}
    9 \cdot 2^s - 9 \cdot 2^{s/2} + 1 &     \mbox{if }s\mbox{ is even}  \\
    8 \cdot 2^s - 6 \cdot 2^{(s+1)/2} + 1 & \mbox{if }s\mbox{ is odd} \\
   \end{matrix}
  \right.
 </math>

([[Insertion sort]]) The worst case of Shell sort is the basic insertion sort (using a single ''h''-step of 1), which requires O(''n''&sup2;) comparisons and exchanges.

An easily computable ''h''-sequence for Shell sort, and a really poor one, is the [[Fibonacci number|Fibonacci Sequence]] (1, 2, 3, 5, 8, 13, 21, ... ),([[On-Line Encyclopedia of Integer Sequences|OEIS]] sequence [http://www.research.att.com/projects/OEIS?Anum=A000045 A000045])  which increases step size in a natural progression.

The best known sequence of increments in terms of the average number of comparisons made is 1, 4, 10, 23, 57, 132, 301, 701 (further increments unknown) ([[On-Line Encyclopedia of Integer Sequences|OEIS]] sequence [http://www.research.att.com/projects/OEIS?Anum=A102549 A102549]) [http://www-zo.iinf.polsl.gliwice.pl/~mciura/shellsort.pdf]. The increments were found empirically; no formula for them is known.

See also [http://www.research.att.com/~njas/sequences/Sindx_So.html#sorting this entry in OEIS's sequences index] for a list of sequences used in shell sorting.

== Implementations ==

=== Using a list of shell sizes ===

The following [[Java_programming_language|Java]] program sorts an array ''a'' from index position 0 through ''n''-1. The number of columns used for arranging data in each step is in array ''cols''. Thus, data are arranged in 4,356,424 columns in the first step and in one column in the last step. Note that essentially nothing is done if the number of columns ''h'' is larger than the number of data elements ''n''. Each column is sorted by insertion sort. First, data of the second row, beginning at ''i'' = ''h'', are sorted to the correct position in their column, then data of the third row (when ''i'' reaches value 2''h'') and so on.

<pre>
void shellsort (int[] a, int n) {
    int[] cols= { 4356424, 1355339, 543749, 213331, 84801, 27901,
                    11969, 4711, 1968, 815, 277, 97, 31, 7, 3, 1 };
    for (int k = 0; k < 16; k++) {
        int h = cols[k];
        for (int i = h; i < n; i++) {
            int v = a[i];
            int j = i;
            while (j >= h && a[j - h] > v) {
                a[j] = a[j - h];
                j = j - h;
            }
            a[j] = v;
        }
    }
}</pre>

=== Using Fibonacci numbers ===

<pre>
void shellsort (int[] a, int n) {
    int h = 1, hh = 1;

    while(hh < n) {
       // eg, h = 5, hh = 8
       hh = hh + h; // hh = 8 + 5 = 13
       h = hh - h;  // h = 13 - 5 = 8
    }

    while(hh > 1) {
        for (int i = h; i < n; i++) {
            int v = a[i];
            int j = i;
            while (j >= h && a[j - h] > v) {
                a[j] = a[j - h];
                j = j - h;
            }
            a[j] = v;
        }

        // e.g., h = 8, hh = 13

        h = hh - h; // h = 13 - 8 = 5
        hh = hh - h; // hh = 13 - 5 = 8
    }
}</pre>

The squares of Fibonacci numbers (1, 4, 9, 25, ...) make an even better sequence.

==References==
[Kn] Donald E. Knuth: ''Sorting and Searching'', vol. 3 of ''[[The Art of Computer Programming]]'', second edition. Addison-Wesley (1998). ISBN 0-201-89685-0<br>
[Se] Robert Sedgewick: ''Algorithms''. Addison-Wesley (1988)<br>
[Sh] Donald L. Shell: ''A high-speed sorting procedure''. [[Communications of the ACM]] 2 (7), 30-32 (1959)

== External links ==
*[http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/shell/shellen.htm Detailed analysis of Shell sort]
* [http://www.nist.gov/dads/HTML/shellsort.html Dictionary of Algorithms and Data Structures: Shellsort]

[[Category:Sort algorithms]]

[[de:Shellsort]]
[[es:Ordenación Shell Sort]]
[[it:Shell sort]]
[[lt:Kevalo r&#363;&#353;iavimo algoritmas]]
[[nl:Shellsort]]
[[ja:&#12471;&#12455;&#12523;&#12477;&#12540;&#12488;]]
[[zh:&#24076;&#23572;&#25490;&#24207;]]