Shell Sort

Shell Sort is an improved version of Insertion Sort. It was invented by Donald Shell in 1959. The main weakness of Insertion Sort is that elements only move one position at a time, so an element that is far from its correct position takes many steps to get there. Shell Sort fixes this by first sorting elements that are far apart from each other, and gradually reducing this "gap" until it becomes 1 (at which point it behaves like a normal Insertion Sort, but on an almost-sorted array).

This technique allows elements to move long distances early on, making the final passes much faster than plain Insertion Sort.

How Shell Sort Works?

  1. Choose a gap sequence (commonly starting at n/2 and halving each time, though other sequences like Knuth's exist).
  2. Divide the array into sub-arrays where elements are gap positions apart from each other.
  3. Perform an Insertion Sort on each of these gapped sub-arrays.
  4. Reduce the gap (commonly gap = gap / 2) and repeat step 2 and 3.
  5. Continue until the gap becomes 1, at which point perform a final normal Insertion Sort pass.

Example: Sorting [12, 34, 54, 2, 3]

Initial array: [12, 34, 54, 2, 3], n = 5

Gap = 2 (5/2 = 2): With gap 2, the array splits into two interleaved sub-sequences that are each sorted using Insertion Sort:

  • Sub-sequence at indices 0, 2, 4: [12, 54, 3] → sorted as [3, 12, 54]
  • Sub-sequence at indices 1, 3: [34, 2] → sorted as [2, 34]

Placing these sorted values back into their original index positions (0,2,4 and 1,3): Array after gap = 2: [3, 2, 12, 34, 54]

Gap = 1 (final pass, normal Insertion Sort):

  • Key = 2 (index 1): 2 < 3, shift 3 → [2, 3, 12, 34, 54]
  • Key = 12 (index 2): 12 > 3, no shift
  • Key = 34 (index 3): 34 > 12, no shift
  • Key = 54 (index 4): 54 > 34, no shift

Final Sorted Array: [2, 3, 12, 34, 54]

GapResulting Array
2[3, 2, 12, 34, 54]
1[2, 3, 12, 34, 54]

Pseudocode

Step 1: Start
Step 2: gap = n / 2
Step 3: While gap > 0:
Step 4:     For i = gap to n-1:
Step 5:         key = array[i]
Step 6:         j = i
Step 7:         While j >= gap AND array[j - gap] > key:
Step 8:             array[j] = array[j - gap]
Step 9:             j = j - gap
Step 10:        array[j] = key
Step 11:    gap = gap / 2
Step 12: End

Advantages

  • Significantly faster than plain Insertion Sort or Selection Sort for medium-sized datasets.
  • In-place algorithm needs no extra array.
  • Adaptive to some degree performs better when data is partially sorted.
  • Simple modification of Insertion Sort, easy to understand once Insertion Sort is known.
  • Useful when recursion (as in Quick Sort/Merge Sort) is undesirable, e.g., in embedded systems with limited stack space.

Disadvantages

  • Not stable the relative order of equal elements can change due to long-distance swaps.
  • Performance heavily depends on the chosen gap sequence; a poor sequence can lead to worse performance.
  • Still slower than O(n log n) algorithms like Merge Sort or Quick Sort for large datasets.
  • Complexity analysis is more difficult since it depends on the gap sequence used.

Time and Space Complexity

CaseTime ComplexityExplanation
Best CaseO(n log n)With a good gap sequence and nearly sorted data
Average CaseO(n log n) to O(n^1.25)Depends on gap sequence (e.g., Knuth's sequence)
Worst CaseO(n²)With a poor gap sequence (e.g., simple n/2 halving in adversarial cases)

Space Complexity: O(1) sorting is performed in-place.

Stability: Not stable In-place: Yes

When to Use Shell Sort?

  • Medium-sized datasets where Insertion Sort or Selection Sort would be too slow but the overhead of Merge Sort/Quick Sort isn't justified.
  • Systems with limited memory or where recursion should be avoided.
  • Embedded systems and low-level libraries where a simple yet reasonably fast algorithm is needed.

Practice Questions

  1. Sort the array [35, 33, 42, 10, 14, 19, 27, 44] using Shell Sort with the gap sequence starting at n/2 and halving each time. Show the array after every gap phase.
  2. Explain, with an example, why Shell Sort is considered "not stable."
  3. For the array [9, 8, 7, 6, 5, 4, 3, 2, 1] and initial gap = 4, show the array after the gap = 4 phase.
  4. Compare the number of comparisons made by Shell Sort versus plain Insertion Sort for the array [6, 5, 4, 3, 2, 1].
  5. Research and describe Knuth's gap sequence. How does it differ from the simple n/2 halving sequence?
  6. Trace Shell Sort on the array [20, 15, 8, 12, 6, 3] using gaps 3, 1 in that order.
  7. Explain why choosing a poor gap sequence can degrade Shell Sort's performance to O(n²).
  8. Write a program to implement Shell Sort using the gap sequence gap = gap/2, and test it on 10 random integers.
  9. Discuss one real-world or practical scenario where Shell Sort might be preferred over Quick Sort.
  10. Given the array [70, 40, 10, 90, 30, 20, 60, 50], manually sort it using Shell Sort with gaps 4, 2, 1 and show the array after each gap phase.
Previous Post
Merge Sort
Next Post
Binary Sort
0 people found this article helpful

Was this article helpful?