How to Do Shell Sort in Python

Introduction

Shell Sort is an efficient, in-place, comparison-based sorting algorithm that generalizes insertion sort by allowing the exchange of items that are far apart. It’s named after its inventor, Donald Shell, who introduced it in 1959. Shell sort is particularly efficient for medium-sized datasets, and its performance depends heavily on the choice of gap sequence. In this blog post, we’ll explain how shell sort works, provide a Python implementation and pseudocode, and discuss its advantages and limitations.

---

What is Shell Sort?

Shell Sort is a generalized version of insertion sort that uses gaps to compare elements farther apart than adjacent ones. By reducing the gap with each iteration, Shell Sort allows elements to move toward their correct positions faster. It’s handy when the input list is large and unsorted.

How Shell Sort Works:

1. Start with a large gap, typically half the size of the array.
2. Perform insertion sort on elements separated by the gap.
3. Reduce the gap until it becomes 1, then finish with a traditional insertion sort.

Shell Sort Pseudocode

ShellSort(array):
    n = length of array   # Get the size of the array
    gap = n // 2          # Initialize the gap as half the array size

    # Loop until the gap is reduced to 0
    while gap > 0:
        # Perform insertion sort for elements that are gap positions apart
        for i = gap to n - 1:
            temp = array[i]  # Store the current element in a temporary variable
            j = i            # Initialize j to the current index

            # Compare elements that are gap apart and shift elements as needed
            while j >= gap and array[j - gap] > temp:
                array[j] = array[j - gap]  # Shift larger elements to the right
                j = j - gap                # Move the index back by the gap

            # Place the temp element in its correct location
            array[j] = temp

        # Reduce the gap for the next iteration
        gap = gap // 2

Key comments explained:

• Initialize the gap: The gap is set to half the array size at first (n // 2), which reduces progressively.
• Perform insertion sort: For each gap, elements that are gap positions apart are compared, and the larger elements are shifted right.
• Gap reduction: After each pass through the array, the gap is halved until it reaches 1 (where the final insertion sort is performed). When the gap becomes 0, the array is sorted.

Time Complexity:

• Best Case: O(n log n) with an optimal gap sequence.
• Worst Case: O(n²) (depends on the gap sequence).
• Average Case: O(n log n) or worse, depending on the gap sequence.

Space Complexity:

• O(1): Shell Sort is an in-place algorithm.

---

Shell Sort Algorithm in Python

Here’s a Python implementation of Shell Sort using Shell’s original gap sequence (n // 2, n // 4, ..., 1):

def shell_sort(arr):
    n = len(arr)
    gap = n // 2

    # Perform shell sort with gap reduction
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            # Perform insertion sort for elements separated by the gap
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2  # Reduce the gap for the next pass

# Example usage:
data = [19, 22, 63, 105, 2, 78, 54, 92, 10, 45, 72, 8, 18, 66, 3]
shell_sort(data)
print("Sorted array:", data)

Output:

Sorted array: [2, 3, 8, 10, 18, 19, 22, 45, 54, 63, 66, 72, 78, 92, 105]

---

Step-by-Step Explanation of Shell Sort

Let’s break down how Shell Sort works for the array [19, 22, 63, 105, 2, 78, 54, 92, 10, 45, 72, 8, 18, 66, 3].

Step 1: Initialize the Gap Sequence

• The initial gap is calculated as half of the array length (n // 2), which is 15 // 2 = 7.

Initial gap: 7

Step 2: Perform Insertion Sort for Elements with Gap 7

• We now compare and swap elements that are 7 positions apart.

Array before sorting:

[19, 22, 63, 105, 2, 78, 54, 92, 10, 45, 72, 8, 18, 66, 3]

• Compare arr[0] (19) and arr[7] (92): No swap.
• Compare arr[1] (22) and arr[8] (10): Swap → [19, 10, 63, 105, 2, 78, 54, 92, 22, 45, 72, 8, 18, 66, 3].
• Compare arr[2] (63) and arr[9] (45): Swap → [19, 10, 45, 105, 2, 78, 54, 92, 22, 63, 72, 8, 18, 66, 3].
• Compare arr[3] (105) and arr[10] (72): Swap → [19, 10, 45, 72, 2, 78, 54, 92, 22, 63, 105, 8, 18, 66, 3].
• Compare arr[4] (2) and arr[11] (8): No swap.
• Compare arr[5] (78) and arr[12] (18): Swap → [19, 10, 45, 72, 2, 18, 54, 92, 22, 63, 105, 8, 78, 66, 3].
• Compare arr[6] (54) and arr[13] (66): No swap.
• Compare arr[7] (92) and arr[14] (3): Swap → [19, 10, 45, 72, 2, 18, 54, 3, 22, 63, 105, 8, 78, 66, 92].

Array after first pass (gap 7):

[19, 10, 45, 72, 2, 18, 54, 3, 22, 63, 105, 8, 78, 66, 92]

---

Step 3: Reduce the Gap

• We reduce the gap by dividing it by 2: 7 // 2 = 3.

New gap: 3

Step 4: Perform Insertion Sort with Gap 3

• Now we compare and swap elements that are 3 positions apart.
• Compare arr[0] (19) and arr[3] (72): No swap.
• Compare arr[1] (10) and arr[4] (2): Swap → [19, 2, 45, 72, 10, 18, 54, 3, 22, 63, 105, 8, 78, 66, 92].
• Compare arr[2] (45) and arr[5] (18): Swap → [19, 2, 18, 72, 10, 45, 54, 3, 22, 63, 105, 8, 78, 66, 92].
• Compare arr[3] (72) and arr[6] (54): Swap → [19, 2, 18, 54, 10, 45, 72, 3, 22, 63, 105, 8, 78, 66, 92].
• Compare arr[4] (10) and arr[7] (3): Swap → [19, 2, 18, 54, 3, 45, 72, 10, 22, 63, 105, 8, 78, 66, 92].
• Compare arr[5] (45) and arr[8] (22): Swap → [19, 2, 18, 54, 3, 22, 72, 10, 45, 63, 105, 8, 78, 66, 92].
• Compare arr[6] (72) and arr[9] (63): Swap → [19, 2, 18, 54, 3, 22, 63, 10, 45, 72, 105, 8, 78, 66, 92].
• Compare arr[7] (10) and arr[10] (105): No swap.
• Compare arr[8] (45) and arr[11] (8): Swap → [19, 2, 18, 54, 3, 22, 63, 10, 8, 72, 105, 45, 78, 66, 92].
• Compare arr[9] (72) and arr[12] (78): No swap.
• Compare arr[10] (105) and arr[13] (66): Swap → [19, 2, 18, 54, 3, 22, 63, 10, 8, 72, 66, 45, 78, 105, 92].
• Compare arr[11] (45) and arr[14] (92): No swap.

Array after second pass (gap 3):

[19, 2, 18, 54, 3, 22, 63, 10, 8, 72, 66, 45, 78, 105, 92]

Step 5: Reduce the Gap to 1 (Final Insertion Sort Pass)

• Now, reduce the gap to 1 (regular insertion sort).

New gap: 1

• Compare adjacent elements and perform insertion sort:
  • Compare arr[0] (19) and arr[1] (2): Swap.
  • Compare arr[1] (19) and arr[2] (18): Swap.
  • Compare arr[2] (19) and arr[3] (54): No swap.
  • Compare arr[3] (54) and arr[4] (3): Swap.
  • Continue swapping as needed until the array is fully sorted.

Array after final pass (gap 1):

[2, 3, 8, 10, 18, 19, 22, 45, 54, 63, 66, 72, 78, 92, 105]

Final Sorted Array:

After completing all the gap reductions, the array is fully sorted:

[2, 3, 8, 10, 18, 19, 22, 45, 54, 63, 66, 72, 78, 92, 105]

---

Similarities and Differences Between Shell Sort and Comb Sort

Similarities:

• Gap-based Comparison: Both algorithms start by comparing elements that are far apart (based on a gap) and gradually reduce the gap.
• In-Place Sorting: Both Shell Sort and Comb Sort operate in-place with O(1) space complexity.
• Improvement over Basic Sorts: Both improve on their respective simpler algorithms—Shell Sort improves insertion sort, while Comb Sort improves bubble sort.

Differences:

• Gap Sequence: Shell Sort typically uses a predetermined sequence like n//2, n//4, ..., 1, while Comb Sort shrinks the gap dynamically using a shrink factor (often 1.3).
• Sorting Approach: Shell Sort applies insertion sort during each pass with a given gap, whereas Comb Sort behaves like bubble sort when comparing elements.
• Time Complexity: Shell Sort can achieve O(n log n) with an optimal gap sequence, whereas Comb Sort typically does not reach O(n log n) performance and remains closer to O(n²).

---

Shell Sort vs. Other Sorting Algorithms

Below, we explore the advantages and trade-offs when compared to other well-known algorithms.

---

1. Shell Sort vs. Insertion Sort

• Performance:
  • Insertion Sort has a time complexity of O(n²), which makes it inefficient for large datasets, especially when the array is unsorted.
  • Shell Sort, by contrast, improves significantly on this by sorting elements far apart first. This helps move elements into better positions early, making subsequent passes of insertion sort much faster. Shell Sort’s average time complexity ranges from O(n log n) to O(n^1.5), depending on the gap sequence.
• Use Case:
  • Use Insertion Sort for small datasets or nearly sorted arrays where its simplicity shines. It’s optimal for nearly sorted data with a best-case time complexity of O(n).
  • Shell Sort is preferable for larger datasets where the elements are more unordered. It mitigates Insertion Sort’s inefficiency by handling far-apart elements before reducing the gap.

---

2. Shell Sort vs. Bubble Sort

• Performance:
  • Bubble Sort is one of the least efficient sorting algorithms, with a worst-case time complexity of O(n²). It operates by repeatedly swapping adjacent elements, making it very slow when the dataset is large and unordered.
  • Shell Sort significantly outperforms Bubble Sort because it reduces the number of swaps by initially working with elements far apart and decreasing the gap, avoiding Bubble Sort’s inefficiency with “turtles” (small elements at the end).
• Use Case:
  • Bubble Sort is rarely used in practice due to its inefficiency, except for educational purposes.
  • Shell Sort is a much better choice than Bubble Sort, providing substantial improvements without adding much complexity.

---

3. Shell Sort vs. Comb Sort

• Gap Control:
  • Both Shell Sort and Comb Sort use gaps to compare elements that are far apart. The main difference is in how they control the gap sequence.
  • Shell Sort uses a predetermined gap sequence (often halving the gap in each step), whereas Comb Sort shrinks the gap dynamically using a shrink factor (commonly 1.3).
• Sorting Method:
  • Shell Sort uses insertion sort for each gap pass, making it ideal for handling nearly sorted subsections as the gap reduces.
  • Comb Sort, on the other hand, operates like a refined bubble sort that compares elements farther apart and works toward removing inefficiencies like turtles early on. It doesn’t achieve the same optimization as insertion sort for small gaps.
• Performance:
  • Shell Sort typically has a better time complexity than Comb Sort, especially with optimal gap sequences, allowing it to approach O(n log n) performance in the best cases. Comb Sort often stays around O(n log n) but is usually slower than Shell Sort.

---

4. Shell Sort vs. Quick Sort

• Performance:
  • Quick sort has a best- and average-case time complexity of O(n log n), which is superior to Shell Sort in most scenarios. However, in the worst case, Quick sort can degrade to O(n²), though this can be mitigated with good pivot selection strategies.
  • Shell Sort, with a good gap sequence, can approach O(n log n) performance, but it’s generally slower than Quick sort on large datasets due to the overhead of multiple gap-based insertion sorts.
• Space Complexity:
  • Shell Sort is an in-place algorithm with O(1) extra space, which makes it more memory efficient than Quick sort, which requires O(log n) space for recursive function calls.
• Use Case:
  • Quick sort is usually faster for very large datasets, but Shell Sort can be more memory-efficient and may outperform Quick sort when working on smaller or medium-sized datasets where memory is constrained.

---

5. Shell Sort vs. Merge Sort

• Performance:
  • Merge Sort guarantees a time complexity of O(n log n), better than Shell Sort’s worst-case time complexity. However, Merge Sort requires additional memory for its auxiliary arrays, resulting in a space complexity of O(n).
  • Shell Sort is not guaranteed to be O(n log n), but with a good gap sequence, it can achieve similar performance, and it requires only O(1) additional space.
• Stability:
  • Merge Sort is a stable sorting algorithm, meaning it preserves the relative order of equal elements. Shell Sort is not stable, as elements can move across gaps and disrupt their relative order.
• Use Case:
  • Use Merge Sort when you need guaranteed O(n log n) performance and stability is important (e.g., when sorting objects by multiple fields).
  • Use Shell Sort when memory is limited, as its in-place sorting makes it more memory-efficient for medium-sized arrays.

---

Advantages of Shell Sort

1. Faster than Insertion Sort: By sorting elements that are farther apart, Shell Sort reduces the number of movements required for elements to reach their final positions.
2. In-Place Sorting: No additional memory is required, making it memory efficient.

---

Limitations of Shell Sort

1. Gap Sequence Sensitive: The efficiency of Shell Sort depends heavily on the choice of gap sequence. Poor sequences lead to slower sorting times.
2. Not Stable: Shell Sort does not preserve the relative order of equal elements, which can be a drawback for some applications.

---

When to Use Shell Sort

• Medium-Sized Datasets: Shell Sort shines with medium-sized unsorted datasets where insertion sort would be too slow, but quick sort might be overkill.
• Memory-Constrained Environments: Since Shell Sort is an in-place sorting algorithm, it’s ideal when memory usage is a concern.

---

Conclusion

Shell Sort is an efficient and flexible sorting algorithm that improves upon insertion sort by introducing a gap sequence. While it may not outperform quick sort or merge sort on large datasets, it’s a great choice for medium-sized arrays, especially when memory efficiency is important. Try the Python code above to experiment with Shell Sort and see how it performs on your data!

Congratulations on reading to the end of this tutorial!

For further reading on sorting algorithms in Python, go to the articles:

• How to do Insertion Sort in Python
• How to Do Bubble Sort in Python
• How to Do Selection Sort in Python
• How to Do Bucket Sort in Python
• How to Do Heap Sort in Python
• How to Do Pigeonhole Sort in Python
• How To Do Comb Sort in Python 

To implement Shell Sort in C++ go to Shell Sort in C++.

Have fun and happy researching!