Shell Sort Algorithm sorts elements in array at a specific interval. At first, it sorts the elements that are away from each other and successively reduces the interval between them. This is a simple but powerful version of another sorting algorithm insertion sort. The performance of the shell sort depends on the type of sequence used for a given list. It performs very well if array elements are near to each other, i.e. array is partially sorted.

Shell Sort is named after Donald Lewis Shell who initially wrote it in a research paper called A High-Speed Sorting Procedure, which was published in Communications of the ACM, July 1959.

How Shell Sort Works?

This sorting algorithm extensively uses Insertion sort to sort the smaller arrays as insertion sort is very efficient on small arrays. It is also very efficient on nearly sorted arrays.

  1. Choose an initial increment interval based on the size of the list.
  2. Choose a smaller interval size (based on sequence) and continue through the loop.
  3. While in the loop, use insertion sort with an interval size 1 to complete the array sorting.
  4. Array is fully sorted when the loop ends.

With each outer iteration of the algorithm, the elements in the array closer to their actual positions. This method is efficient due to the use of insertion sort. It utilize the order present in a partially sorted input array. It is important to choose a good sequence of intervals.

Here are some of the good intervals used in Shell Sort.

Shell Sort Sequence Intervals

Donald Shell’s Actual Interval:

Formula: [N/2k]

Sequence: [N/2], [N/4], [N/8], … 1

Hibbard, Papernov & Stasevich Interval:

Both of them introduced similar intervals with minor changes i.e.

Hibbard’s Interval:

Formula: 2k-1

Sequence: 0, 1, 3, 7, 15, 31

Papernov & Stasevich’s Interval:

Formula: 2k+1, starting with 1

Sequence: 1, 3, 5, 9, 17, 33, 65,

Pratt’s Interval:

These numbers were once called “harmonic numbers”.

Formula: 2^i*3^j with i, j >= 0

Sequence: 1, 2, 3, 4, 6, 8, 9, 12, 16,

Knuth’s Interval:

Formula: (3^n – 1)/2

Sequence: 0, 1, 4, 13, 40, 121, 364,

Sedgewick’s Intervals:

Formula 1: 4^(n+1) + 3*2^n + 1

Sequence: 1, 8, 23, 77, 281, 1073, 4193

Formula 2 – Good sequence of intervals for Shell sort. It is even best on arrays with more values.

For Arrays with Even Length:

9*2^n – 9*2^(n/2) + 1

For Arrays with Odd Length:

8*2^n – 6*2^((n+1)/2) + 1

Sequence 2:

1, 5, 19, 41, 109, 209, 505, 929, 2161

Tokuda’s Intervals:

Formula: ceiling( (9 * (9/4)^n – 4) / 5).

Sequence: 1, 4, 9, 20, 46, 103, 233,

Ciura’s Interval:

Best Increments for the Average Case of Shell sort.

Sequence: 1, 4, 10, 23, 57, 132, 301, 701, 1750

Shell Sort Applications

  • Shell sort is used in the Linux Kernel.
  • Shell sort is used in Linux kernel library uClib, which is used in embedded systems.
  • It also used in bzip2 compression library using Knuth’s increments.
  • It is relatively easy to implement and does not use any additional memory (other than input).

Shell Sort Complexity

Worst Case Complexity: <= O(n2)

Best Case Complexity: O(n*log n)

Average Case Complexity: O(n*log n)

Space Complexity is O(1)

Shell Sort Implementation using Knuth’s Interval

Output Knuth’s Implementation

Shell Sort Implementation using Hibbard’s Sequence

Output of Shell Sort with Hibbard’s Sequence