{"title":"Shell Sort","description":"","content":"Shell Sort is an optimization of Insertion Sort designed to handle larger inputs more efficiently. Instead of comparing adjacent elements right away, it starts by comparing elements that are far apart, gradually reducing the gap between them. This allows the algorithm to move elements closer to their correct positions early on.\n\nBy the time the gap becomes 1, the array is already partially sorted, making the final pass much faster than a regular Insertion Sort. This simple idea significantly improves performance in practice.\n\nIn this chapter, you will learn how Shell Sort works, how the gap sequence affects its performance, and how to implement it. You will also understand why it performs better than basic quadratic sorting algorithms in many real-world scenarios.\n\n---\n\n# What Is Shell Sort?\n\nShell sort is a generalization of insertion sort that allows the exchange of elements that are far apart. Instead of comparing adjacent elements, it compares elements separated by a \"gap\" and uses insertion sort on each group of elements spaced by that gap. Over successive passes, the gap shrinks until it reaches 1, at which point the algorithm performs a standard insertion sort on an array that is already nearly sorted.\n\nThe key idea is this: by sorting elements that are far apart early on, we eliminate large amounts of disorder in the array quickly. Each pass with a smaller gap brings the array closer to sorted order. By the time the gap reaches 1, most elements are already close to their final positions, so the last pass runs in nearly O(n) time.\n\nHere is how Shell sort compares elements at different gap values versus regular insertion sort:\n\n\n```mermaid\nflowchart TD\n subgraph IS[\"Insertion Sort (gap = 1)\"]\n A1[\"8\"] --- A2[\"3\"] --- A3[\"5\"] --- A4[\"1\"] --- A5[\"9\"] --- A6[\"2\"] --- A7[\"7\"] --- A8[\"4\"]\n end\n\n subgraph SS4[\"Shell Sort Pass 1 (gap = 4)\"]\n B1[\"8\"] -.- B5[\"9\"]\n B2[\"3\"] -.- B6[\"2\"]\n B3[\"5\"] -.- B7[\"7\"]\n B4[\"1\"] -.- B8[\"4\"]\n end\n\n subgraph SS2[\"Shell Sort Pass 2 (gap = 2)\"]\n C1[\"8\"] -.- C3[\"5\"] -.- C5[\"9\"] -.- C7[\"7\"]\n C2[\"2\"] -.- C4[\"1\"] -.- C6[\"3\"] -.- C8[\"4\"]\n end\n\n style IS fill:#ff8787,stroke:#000,color:#000\n style SS4 fill:#00ceff,stroke:#000,color:#000\n style SS2 fill:#69db7c,stroke:#000,color:#000\n```\n\n\nIn insertion sort, each element can only compare with its immediate neighbor. Shell sort breaks this restriction by comparing elements separated by a gap. Elements in the same gap-group get sorted together, so large displacements are resolved early.\n\n**Why this matters:** Insertion sort runs in O(n^2) because elements can only move one position per comparison. If an element needs to travel n positions, it takes n swaps. Shell sort lets elements jump across large distances in a single step, dramatically reducing the total number of operations.\n\n---\n\n# How Shell Sort Works\n\nThe algorithm follows a simple three-level loop structure:\n\n1. **Choose a starting gap** (typically n/2, where n is the array size)\n2. **Perform a gapped insertion sort** for the current gap value\n3. **Reduce the gap** (typically by half) and repeat until gap = 1\n\nWhen the gap is larger than 1, the algorithm groups elements that are `gap` positions apart and sorts each group using insertion sort. As the gap decreases, the groups overlap more and more. By the time the gap reaches 1, we are doing a standard insertion sort, but on an array that is already nearly sorted.\n\n### Gap Sequences\n\nThe choice of gap sequence has a significant impact on performance. Different sequences yield different time complexities:\n\n\n| Gap Sequence | Formula | Example (n=16) | Worst-Case Time |\n|--------------|---------|-----------------|-----------------|\n| **Shell's original** | n/2, n/4, ..., 1 | 8, 4, 2, 1 | O(n^2) |\n| **Knuth's** | (3^k - 1) / 2 | 1, 4, 13, 40, 121, ... | O(n^(3/2)) |\n| **Hibbard's** | 2^k - 1 | 1, 3, 7, 15, 31, ... | O(n^(3/2)) |\n| **Sedgewick's** | 4^k + 3*2^(k-1) + 1 | 1, 5, 19, 41, 109, ... | O(n^(4/3)) |\n| **Tokuda's** | ceil((9*(9/4)^k - 4) / 5) | 1, 4, 9, 20, 46, ... | Unknown (empirically fast) |\n\n\nShell's original sequence (n/2) is the simplest and most commonly taught, but it is not the most efficient. Knuth's and Sedgewick's sequences perform better in practice because they avoid the issue of \"increment interaction,\" where certain gap values fail to compare elements that were already compared in previous passes.\n\nFor interviews and most practical purposes, Shell's original sequence (dividing by 2 each time) is perfectly acceptable. Just be aware that better sequences exist.\n\n### The Algorithm Step by Step\n\n\n```mermaid\nflowchart TD\n A[\"Start: gap = n / 2\"] --> B{\"gap > 0?\"}\n B -- Yes --> C[\"For i = gap to n-1\"]\n C --> D[\"Save arr[i] as temp\"]\n D --> E[\"j = i\"]\n E --> F{\"j >= gap AND
arr[j - gap] > temp?\"}\n F -- Yes --> G[\"arr[j] = arr[j - gap]
j = j - gap\"]\n G --> F\n F -- No --> H[\"arr[j] = temp\"]\n H --> I{\"More elements
in this pass?\"}\n I -- Yes --> C\n I -- No --> J[\"gap = gap / 2\"]\n J --> B\n B -- No --> K[\"Array is sorted\"]\n\n style A fill:#00ceff,stroke:#000,color:#000\n style B fill:#ffa94d,stroke:#000,color:#000\n style C fill:#38d9a9,stroke:#000,color:#000\n style D fill:#38d9a9,stroke:#000,color:#000\n style E fill:#38d9a9,stroke:#000,color:#000\n style F fill:#ffa94d,stroke:#000,color:#000\n style G fill:#ff8787,stroke:#000,color:#000\n style H fill:#69db7c,stroke:#000,color:#000\n style I fill:#ffa94d,stroke:#000,color:#000\n style J fill:#00ceff,stroke:#000,color:#000\n style K fill:#69db7c,stroke:#000,color:#000\n```\n\n\nThe outer loop controls the gap, the middle loop iterates through elements starting from index `gap`, and the inner loop performs the gapped insertion sort. This inner loop is identical to insertion sort, except instead of comparing with the previous element (j-1), it compares with the element `gap` positions back (j-gap).\n\nWhen the gap finally reaches 1, the algorithm performs one last pass of standard insertion sort. But because the earlier passes have already moved elements close to their final positions, this last pass does very little work, typically running in close to O(n) time.\n\n---\n\n# Code Implementation\n\n\n```java\npublic class ShellSort {\n public static void shellSort(int[] arr) {\n int n = arr.length;\n\n // Start with a large gap and reduce it\n for (int gap = n / 2; gap > 0; gap /= 2) {\n // Perform gapped insertion sort for this gap size\n for (int i = gap; i < n; i++) {\n int temp = arr[i];\n int j = i;\n\n // Shift earlier gap-sorted elements up until\n // the correct location for arr[i] is found\n while (j >= gap && arr[j - gap] > temp) {\n arr[j] = arr[j - gap];\n j -= gap;\n }\n\n arr[j] = temp;\n }\n }\n }\n}\n```\n\n```python\ndef shell_sort(arr):\n n = len(arr)\n gap = n // 2\n\n while gap > 0:\n for i in range(gap, n):\n temp = arr[i]\n j = i\n\n # Shift earlier gap-sorted elements up\n while j >= gap and arr[j - gap] > temp:\n arr[j] = arr[j - gap]\n j -= gap\n\n arr[j] = temp\n\n gap //= 2\n```\n\n```cpp\n#include \n\nvoid shellSort(std::vector& arr) {\n int n = arr.size();\n\n for (int gap = n / 2; gap > 0; gap /= 2) {\n for (int i = gap; i < n; i++) {\n int temp = arr[i];\n int j = i;\n\n while (j >= gap && arr[j - gap] > temp) {\n arr[j] = arr[j - gap];\n j -= gap;\n }\n\n arr[j] = temp;\n }\n }\n}\n```\n\n```csharp\npublic class ShellSort {\n public static void Sort(int[] arr) {\n int n = arr.Length;\n\n for (int gap = n / 2; gap > 0; gap /= 2) {\n for (int i = gap; i < n; i++) {\n int temp = arr[i];\n int j = i;\n\n while (j >= gap && arr[j - gap] > temp) {\n arr[j] = arr[j - gap];\n j -= gap;\n }\n\n arr[j] = temp;\n }\n }\n }\n}\n```\n\n```javascript\nfunction shellSort(arr) {\n const n = arr.length;\n\n for (let gap = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {\n for (let i = gap; i < n; i++) {\n const temp = arr[i];\n let j = i;\n\n while (j >= gap && arr[j - gap] > temp) {\n arr[j] = arr[j - gap];\n j -= gap;\n }\n\n arr[j] = temp;\n }\n }\n\n return arr;\n}\n```\n\n```typescript\nfunction shellSort(arr: number[]): number[] {\n const n: number = arr.length;\n\n for (let gap: number = Math.floor(n / 2); gap > 0; gap = Math.floor(gap / 2)) {\n for (let i: number = gap; i < n; i++) {\n const temp: number = arr[i];\n let j: number = i;\n\n while (j >= gap && arr[j - gap] > temp) {\n arr[j] = arr[j - gap];\n j -= gap;\n }\n\n arr[j] = temp;\n }\n }\n\n return arr;\n}\n```\n\n\nThe algorithm itself is short, with no recursion and no auxiliary data structures. This simplicity is one of Shell sort's biggest advantages.\n\n---\n\n# Example Walkthrough\n\nLet us trace through Shell sort on the array `[12, 34, 54, 2, 3]` using Shell's original gap sequence (n/2).\n\n**Initial array:** `[12, 34, 54, 2, 3]`, n = 5\n\n### Pass 1: gap = 2\n\nWith gap = 2, we are sorting elements that are 2 positions apart. This creates the following interleaved sub-arrays:\n\n- **Sub-array 1** (indices 0, 2, 4): `[12, 54, 3]`\n- **Sub-array 2** (indices 1, 3): `[34, 2]`\n\n\n```mermaid\nflowchart LR\n subgraph Array[\"Array with gap = 2\"]\n I0[\"[0] 12\"]\n I1[\"[1] 34\"]\n I2[\"[2] 54\"]\n I3[\"[3] 2\"]\n I4[\"[4] 3\"]\n end\n\n I0 -.- I2 -.- I4\n I1 -.- I3\n\n style I0 fill:#00ceff,stroke:#000,color:#000\n style I2 fill:#00ceff,stroke:#000,color:#000\n style I4 fill:#00ceff,stroke:#000,color:#000\n style I1 fill:#ffa94d,stroke:#000,color:#000\n style I3 fill:#ffa94d,stroke:#000,color:#000\n```\n\n\nNow we walk through each element starting from index `gap = 2`:\n\n**i = 2:** temp = 54, j = 2\n\n- Compare arr[0] = 12 with temp = 54. Since 12 < 54, no shift needed.\n- arr[2] = 54 (unchanged)\n- Array: `[12, 34, 54, 2, 3]`\n\n**i = 3:** temp = 2, j = 3\n\n- Compare arr[1] = 34 with temp = 2. Since 34 > 2, shift: arr[3] = 34, j = 1.\n- j = 1 < gap = 2, so stop.\n- arr[1] = 2\n- Array: `[12, 2, 54, 34, 3]`\n\n**i = 4:** temp = 3, j = 4\n\n- Compare arr[2] = 54 with temp = 3. Since 54 > 3, shift: arr[4] = 54, j = 2.\n- Compare arr[0] = 12 with temp = 3. Since 12 > 3, shift: arr[2] = 12, j = 0.\n- j = 0 < gap = 2, so stop.\n- arr[0] = 3\n- Array: `[3, 2, 12, 34, 54]`\n\nAfter gap = 2, the sub-arrays are sorted:\n\n- Sub-array 1 (indices 0, 2, 4): `[3, 12, 54]` (was `[12, 54, 3]`)\n- Sub-array 2 (indices 1, 3): `[2, 34]` (was `[34, 2]`)\n\nThe array `[3, 2, 12, 34, 54]` is already much more ordered than the original. Large elements moved to the right, small elements moved to the left.\n\n### Pass 2: gap = 1\n\nThis is standard insertion sort, but on a nearly sorted array.\n\n**i = 1:** temp = 2, j = 1\n\n- Compare arr[0] = 3 with temp = 2. Since 3 > 2, shift: arr[1] = 3, j = 0.\n- arr[0] = 2\n- Array: `[2, 3, 12, 34, 54]`\n\n**i = 2:** temp = 12, j = 2\n\n- Compare arr[1] = 3 with temp = 12. Since 3 < 12, no shift.\n- Array: `[2, 3, 12, 34, 54]`\n\n**i = 3:** temp = 34, j = 3\n\n- Compare arr[2] = 12 with temp = 34. Since 12 < 34, no shift.\n- Array: `[2, 3, 12, 34, 54]`\n\n**i = 4:** temp = 54, j = 4\n\n- Compare arr[3] = 34 with temp = 54. Since 34 < 54, no shift.\n- Array: `[2, 3, 12, 34, 54]`\n\n**Final sorted array:** `[2, 3, 12, 34, 54]`\n\nNotice how the gap = 1 pass only needed one swap (moving 2 before 3). The heavy lifting was done in the gap = 2 pass. This is exactly why Shell sort is faster than plain insertion sort: the final pass operates on an almost-sorted array.\n\n\n```mermaid\nflowchart LR\n subgraph Original[\"Original\"]\n O1[\"12\"] --- O2[\"34\"] --- O3[\"54\"] --- O4[\"2\"] --- O5[\"3\"]\n end\n\n subgraph AfterGap2[\"After gap = 2\"]\n G1[\"3\"] --- G2[\"2\"] --- G3[\"12\"] --- G4[\"34\"] --- G5[\"54\"]\n end\n\n subgraph AfterGap1[\"After gap = 1 (sorted)\"]\n F1[\"2\"] --- F2[\"3\"] --- F3[\"12\"] --- F4[\"34\"] --- F5[\"54\"]\n end\n\n Original --> AfterGap2 --> AfterGap1\n\n style Original fill:#ff8787,stroke:#000,color:#000\n style AfterGap2 fill:#ffa94d,stroke:#000,color:#000\n style AfterGap1 fill:#69db7c,stroke:#000,color:#000\n```\n\n\n---\n\n# Complexity Analysis\n\nShell sort's complexity is unique among sorting algorithms because it depends heavily on the gap sequence, not just the input.\n\n### Time Complexity\n\n\n| Gap Sequence | Worst Case | Average Case | Best Case |\n|--------------|-----------|--------------|-----------|\n| Shell's (n/2) | O(n^2) | O(n^(3/2)) | O(n log n) |\n| Knuth's (3h+1) | O(n^(3/2)) | O(n^(7/6)) | O(n log n) |\n| Hibbard's (2^k - 1) | O(n^(3/2)) | O(n^(5/4)) | O(n log n) |\n| Sedgewick's | O(n^(4/3)) | O(n^(7/6)) | O(n log n) |\n\n\n**Best case (O(n log n)):** When the array is already sorted, each gap pass makes one comparison per element without any shifts. Since there are O(log n) gap values, the total is O(n log n).\n\n**Worst case with Shell's sequence (O(n^2)):** This happens when the gap sequence causes redundant comparisons. For example, with gaps 8, 4, 2, 1, elements at odd indices are never compared with elements at even indices until the very last pass, which then degenerates into a slow insertion sort.\n\n**Why better sequences help:** Knuth's and Sedgewick's sequences are designed so that consecutive gap values share fewer common factors. This ensures that each pass compares elements that previous passes missed, leading to better performance.\n\n### Space Complexity\n\nShell sort uses **O(1)** auxiliary space. It sorts in-place, using only a single temporary variable for the insertion sort swap. This makes it one of the most memory-efficient sorting algorithms.\n\n### Stability\n\nShell sort is **not stable**. Equal elements may change their relative order during gapped passes. Consider two equal elements at positions 0 and 3 with gap = 2. They belong to different sub-arrays and might be rearranged relative to each other.\n\nHere is a summary comparing Shell sort with related algorithms:\n\n\n| Property | Insertion Sort | Shell Sort | Merge Sort | Quick Sort |\n|----------|---------------|------------|------------|------------|\n| Best Case | O(n) | O(n log n) | O(n log n) | O(n log n) |\n| Average Case | O(n^2) | O(n^(3/2))* | O(n log n) | O(n log n) |\n| Worst Case | O(n^2) | O(n^(3/2))* | O(n log n) | O(n^2) |\n| Space | O(1) | O(1) | O(n) | O(log n) |\n| Stable | Yes | No | Yes | No |\n| In-Place | Yes | Yes | No | Yes |\n| Recursive | No | No | Yes | Yes |\n\n\n*With Knuth's gap sequence. Shell's original sequence gives O(n^2) worst case.\n\n---\n\n# When to Use Shell Sort\n\n### Good Use Cases\n\n- **Medium-sized arrays (hundreds to low thousands of elements):** Shell sort outperforms insertion sort significantly and has lower overhead than merge sort or quick sort for moderate input sizes.\n- **Embedded systems and constrained environments:** No recursion means no risk of stack overflow, and O(1) space means no extra memory allocation. This makes Shell sort a solid choice for microcontrollers and systems with limited resources.\n- **When insertion sort is too slow but you want simplicity:** Shell sort's code is barely more complex than insertion sort. If you need a quick performance boost without implementing a full divide-and-conquer algorithm, Shell sort is the natural next step.\n- **Nearly sorted data:** Like insertion sort, Shell sort performs well on data that is already partially ordered. The initial passes have little work to do, and the final pass is nearly O(n).\n- **As a component in hybrid sorting algorithms:** Some implementations of introspective sort use Shell sort for small partitions instead of insertion sort because it handles slightly larger sub-arrays more efficiently.\n\n### Poor Use Cases\n\n- **Very large datasets (millions of elements):** For large inputs, O(n log n) algorithms like merge sort, quick sort, or heap sort are significantly faster. Shell sort cannot compete at that scale.\n- **When stability is required:** If you need equal elements to maintain their original order, Shell sort is not the right choice. Use merge sort or Timsort instead.\n- **When worst-case guarantees matter:** Shell sort's worst case depends on the gap sequence and is hard to pin down precisely. If you need guaranteed O(n log n) performance, use merge sort or heap sort.\n- **Linked lists:** Shell sort relies on random access to elements at arbitrary gap distances. Linked lists do not support efficient random access, making Shell sort impractical for them.","pageType":"dsa"}

Shell Sort

Ashish Pratap Singh

Get Premium