Editing Shellsort (section)

== Description ==
Shellsort is an optimization of [[insertion sort]] that allows the exchange of items that are far apart. The idea is to arrange the list of elements so that, starting anywhere, taking every ''h''th element produces a sorted list. Such a list is said to be ''h''-sorted. It can also be thought of as ''h'' interleaved lists, each individually sorted.<ref name="Sedgewick">
 {{Cite book
  |last=Sedgewick
  |first=Robert
  |author-link=Robert Sedgewick (computer scientist)
  |title=Algorithms in C
  |edition=3rd
  |volume=1
  |publisher=Addison-Wesley
  |year=1998
  |pages=[https://archive.org/details/algorithmsinc00sedg/page/273 273–281]
  |isbn=978-0-201-31452-6
  |url-access=registration
  |url=https://archive.org/details/algorithmsinc00sedg/page/273
  }}</ref> Beginning with large values of ''h'' allows elements to move long distances in the original list, reducing large amounts of disorder quickly, and leaving less work for smaller ''h''-sort steps to do.<ref name="KR">
 {{Cite book
  |last1=Kernighan
  |first1=Brian W.
  |author-link1=Brian Kernighan
  |last2=Ritchie
  |first2=Dennis M.
  |author-link2=Dennis Ritchie
  |title=The C Programming Language
  |edition=2nd
  |publisher=Prentice Hall
  |year=1996
  |pages=62
  |isbn=978-7-302-02412-5
 }}</ref> If the list is then ''k-sorted'' for some smaller integer ''k'', then the list remains ''h''-sorted. A final sort with ''h''&nbsp;=&nbsp;1 ensures the list is fully sorted at the end,<ref name="Sedgewick"/> but a judiciously chosen decreasing sequence of ''h'' values leaves very little work for this final pass to do.

In simplistic terms, this means if we have an array of 1024 numbers, our first gap (''h'') could be 512. We then run through the list comparing each element in the first half to the element in the second half. Our second gap (''k'') is 256, which breaks the array into four sections (starting at 0, 256, 512, 768), and we make sure the first items in each section are sorted relative to each other, then the second item in each section, and so on. In practice the gap sequence could be anything, but the last gap is always 1 to finish the sort (effectively finishing with an ordinary insertion sort).

An example run of Shellsort with gaps 5, 3 and 1 is shown below.

{|class="wikitable" style="text-align:center"
!
! {{mvar|a}}<sub>1</sub> || {{mvar|a}}<sub>2</sub> || {{mvar|a}}<sub>3</sub> || {{mvar|a}}<sub>4</sub>
! {{mvar|a}}<sub>5</sub> || {{mvar|a}}<sub>6</sub> || {{mvar|a}}<sub>7</sub> || {{mvar|a}}<sub>8</sub>
! {{mvar|a}}<sub>9</sub> || {{mvar|a}}<sub>10</sub> || {{mvar|a}}<sub>11</sub> || {{mvar|a}}<sub>12</sub>
|-
! Input data
| 62 || 83 || 18 || 53 || 07 || 17 || 95 || 86 || 47 || 69 || 25 || 28
|-
! After 5-sorting
|                   17 ||                   28 ||                   18 ||                   47 ||                   07
|bgcolor=lightcyan| 25 ||bgcolor=lightcyan| 83 ||bgcolor=lightcyan| 86 ||bgcolor=lightcyan| 53 ||bgcolor=lightcyan| 69
|                   62 ||                   95
|-
! After 3-sorting
|                   17 ||                   07 ||                   18
|bgcolor=lightcyan| 47 ||bgcolor=lightcyan| 28 ||bgcolor=lightcyan| 25
|                   69 ||                   62 ||                   53
|bgcolor=lightcyan| 83 ||bgcolor=lightcyan| 86 ||bgcolor=lightcyan| 95
|-
! After 1-sorting
| 07 ||bgcolor=lightcyan| 17 || 18 ||bgcolor=lightcyan| 25 || 28 ||bgcolor=lightcyan| 47 || 53 ||bgcolor=lightcyan| 62 || 69 ||bgcolor=lightcyan| 83 || 86 ||bgcolor=lightcyan| 95
|}

The first pass, 5-sorting, performs insertion sort on five  separate subarrays (''a''<sub>1</sub>, ''a''<sub>6</sub>, ''a''<sub>11</sub>), (''a''<sub>2</sub>, ''a''<sub>7</sub>, ''a''<sub>12</sub>), (''a''<sub>3</sub>, ''a''<sub>8</sub>), (''a''<sub>4</sub>, ''a''<sub>9</sub>), (''a''<sub>5</sub>, ''a''<sub>10</sub>). For instance, it changes the subarray (''a''<sub>1</sub>, ''a''<sub>6</sub>, ''a''<sub>11</sub>) from (62, 17, 25) to (17, 25, 62). The next pass, 3-sorting, performs insertion sort on the three subarrays (''a''<sub>1</sub>, ''a''<sub>4</sub>, ''a''<sub>7</sub>, ''a''<sub>10</sub>), (''a''<sub>2</sub>, ''a''<sub>5</sub>, ''a''<sub>8</sub>, ''a''<sub>11</sub>), (''a''<sub>3</sub>, ''a''<sub>6</sub>, ''a''<sub>9</sub>, ''a''<sub>12</sub>). The last pass, 1-sorting, is an ordinary insertion sort of the entire array (''a''<sub>1</sub>,..., ''a''<sub>12</sub>).

As the example illustrates, the subarrays that Shellsort operates on are initially short; later they are longer but almost ordered. In both cases insertion sort works efficiently.

Unlike [[insertion sort]], Shellsort is not a [[sorting algorithm#Stability|stable sort]] since gapped insertions transport equal elements past one another and thus lose their original order. It is an [[Adaptive sort|adaptive sorting algorithm]] in that it executes faster when the input is partially sorted.