Shell Sort

by codecrucks · Published 11/09/2021 · Updated 08/06/2022

It is also known as diminishing increment sort. Like selection sort, bubble sort and insertion sort, shell sort is also a comparison based in-place sorting algorithm.

It sorts groups of elements separated by a large gap, progressively gap between two elements reduces. Starting with a larger gap can move some out of order elements into correct location faster than a simple neighbor exchange approach. Shell sort is not stable.

Numbers of passes are controlled by the user. Initially, groups of elements separated by a distance gap are sorted using insertion sort. In the next pass, the distance gap is reduced and groups of elements separated by distance updated gap are sorted using insertion sort. This process continues till gap becomes one. Input to the last pass is nearly sorted elements. They are sorted using insertion sort.

How Shell Sort Works?

Shell sort is an insertion sort optimization that allows for the exchange of items that are widely apart.

The goal is to organize the list of items in such a way that beginning anywhere and taking every h-th member results in a sorted list. A list of this type is said to be h-sorted. It is also possible to think of it as h interleaved lists, each independently sorted.

Starting with big h values allows items to move great distances in the initial list, swiftly eliminating substantial quantities of disorder and leaving less work for smaller h-sort steps to complete. If the list is then k-sorted for any smaller integer k, it will still be h-sorted.

The sequence used reduces the gap between the elements. The following are some examples of optimum sequences that may be utilized in the shell sort algorithm:

Shell’s original sequence: N/2 , N/4 , …, 1
Knuth’s increments: 1, 4, 13, …, (3^k – 1) / 2
Sedgewick’s increments: 1, 8, 23, 77, 281, 1073, 4193, 16577...4j + 1 + 3·2j + 1
Hibbard’s increments: 1, 3, 7, 15, 31, 63, 127, 255, 511…
Papernov & Stasevich increment: 1, 3, 5, 9, 17, 33, 65,...
Pratt: 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81....

In 1959, Donald Shell published the first version of this type. Shel sort’s execution time is greatly influenced by the gap sequence it uses.

Example of Shell Sort

Problem: Sort given array A { 61, 81, 16, 50, 02, 18, 91, 81, 44, 70, 22, 27 } using shell sort with gap value 5, 3 and 1

Solution:

Array A contains 12 elements { a₀,a₁,a₂,_…,a₁₁}.

First pass with gap = 5, performs insertion sort on groups {a₀,a₅,a₁₀}, {a₁, a₆, a₁₁}, {a₂,a₇,}, {a₃,a_8,} and {a₄,a₉}.

Sub array {a₀,a₅,a₁₀} = {61, 18, 22} becomes {18, 22, 61} after first pass

Sub array {a₁, a₆, a₁₁} = {82, 91, 27} becomes {27, 82, 91} after first pass

Sub array {a₂, a₇} = {16, 81} remains as it is after first pass

Sub array {a₃, a₈} = {50, 44} becomes {44, 50} after first pass

Sub array {a₄, a₉} = {02, 70} remains as it is after first pass

Below table shows the output after first pass :

	a₀	a₁	a₂	a₃	a₄	a₅	a₆	a₇	a₈	a₉	A₁₀	a₁₁
Input sequence	61	82	16	50	02	18	91	81	44	70	22	27
Grouping	61	82	16	50	02	18	91	81	44	70	22	27
After 5-sorting	18	27	16	44	02	22	82	81	50	70	61	91

The second pass with gap = 3 performs insertion sort on groups {a₀,a₃, a₆, a₉}, {a₁, a₄, a₇, a₁₀}, {a₂, a₅, a₈, a₁₁}.

Sub array {a₀,a₃,a₆,a₉} = {18, 44, 82, 70} becomes {18, 44, 70, 82} after second pass

Sub array {a₁,a₄,a₇,a₁₀} = {27, 02, 81, 61} becomes {02, 27, 61, 81} after second pass

Sub array {a₂,a₅,a₈,a₁₁} = {16, 22, 50, 91} remains as it is after second pass

Below table shows the output after first pass :

	a₀	a₁	a₂	a₃	a₄	a₅	a₆	a₇	a₈	a₉	A₁₀	a₁₁
After 5-sorting	18	27	16	44	02	22	82	81	50	70	61	91
Grouping	18	27	16	44	02	22	82	81	50	70	61	91
After 3-sorting	18	02	16	44	27	22	70	61	50	82	81	91

The third pass performs normal insertion sort on a group of elements {a₀,a₁,a₂,_…,a₁₁}. The list would be sorted after this pass.

Output of 3^rd pass is : {02, 16, 18, 22, 27, 44, 50, 61, 70, 81, 82, 91}

Algorithm of Shell Sort

Algorithm SHELL_SHORT(A)
// A is an array of size n

for gap ← n/2 to gap > 0 do
  for p ← gap to p < n do
    tmp ← a[p]
    for j ← p to (j ≥ gap && tmp < a[j – gap]) do
      a[j] ← a[j – gap]
      j ← j – gap 
    end
    a[j] ← tmp
    p ← p + 1
  end
  gap ← gap/2
end

Complexity Analysis

Worst Case Complexity: less than or equal to O(n²)
Worst case complexity for shell sort is always less than or equal to O(n²).
According to Poonen Theorem, worst case complexity for shell sort is Θ(N log N)²/(log log N)²) or Θ(Nlog N)²/log log N) or Θ(N(log N)²) or something in between.
Best Case Complexity: O(n*log n)
When the array is already sorted, the total number of comparisons for each interval (or increment) is equal to the size of the array.
Average Case Complexity: O(n*log n)
It is around O(n^1.25).
The complexity is determined by the interval used. The difficulties listed above vary depending on the increment sequence used. The optimal increment sequence is unknown.
Insertion sort is effective for small list or list having almost sorted sequence. In shell sort, groups are initially small, later they become larger but are nearly sorted. So insertion sort works nearly in linear order. Shell sort is adaptive; it runs faster for nearly sorted data.
Running time of this approach heavily depends on the gap sequence. For gap sequence n/2, n/4, …1 algorithm operates in quadratic time and its complexity is O(n²). For gap sequence 1, 3, 7, 15, 31, 63, …. and 1, 3, 5, 9, 17, 33, 65, … it runs in O(n^3/2) time. Mathematicians have proposed many other classes of running time of shell sort with different gap sequences.

Simulation of Shell Sort

Initially, elements separated by gap 5 are sorted using insertion sort. Then gap is reduced to 1.

Shell sort example — Simulation of Shell Sort

Image Source: https://blogs.cuit.columbia.edu/zp2130/files/2018/12/Shell_Sort.gif [link]

Discussion and Comparison

Shellsort is not a stable algorithm: it can modify the relative order of elements with equal values.

It is an adaptive sorting algorithm in the sense that it runs quicker when the input is halfway sorted.

When the close elements are far apart, insertion sort does not function effectively. Shell sorting aids in shortening the distance between adjacent elements. As a result, there will be fewer swapping’s to perform.

Shellsort performs more operations and has higher cache miss ratio than quicksort. However, since it can be implemented using little code and does not use the call stack, is is prefered in embedded device over quick sort.

Shellsort is, for example, used in the uClibc library For similar reasons, in the past, Shellsort was used in the Linux kernel.

Some Popular Sorting Algorithms

Following are the few popular sorting algorithms used in computer science: