We previously learned about Insertion Sort, which is highly efficient when most elements in the array are already sorted. However, if the array is completely unsorted or reversed, Insertion Sort can only move one element at a time, making it relatively inefficient. Shell Sort is an improved version of Insertion Sort that improves efficiency by first making the array mostly sorted through grouping and then applying Insertion Sort to the entire array.

Basic Idea of Shell Sort¶

The core of Shell Sort is “grouping” and “Insertion Sort”. Unlike Insertion Sort, which only compares adjacent elements, Shell Sort divides the array into several groups where elements within each group are spaced by a certain distance (called the “increment” or “step size”). Insertion Sort is then applied to each group. As the increment gradually decreases, the groups become finer, and by the time the increment reaches 1, the entire array is already mostly sorted, allowing Insertion Sort to complete quickly.

Steps of Shell Sort¶

1. Select Initial Increment: Typically, the initial increment is half the length of the array (n//2), and then the increment is halved in each subsequent iteration until it becomes 0.
2. Grouping and Insertion Sort: For each increment gap, the array is divided into gap groups, where elements in each group have indices differing by gap. For example, if the array length is 10 and gap=3, Group 1 contains indices 0, 3, 6, 9; Group 2 contains 1, 4, 7; Group 3 contains 2, 5, 8. Insertion Sort is then applied to each group.
3. Adjust Increment Repeatedly: When the increment is reduced to 1, the entire array is already mostly sorted, and Insertion Sort can complete quickly.

Code Implementation (Python)¶

def shell_sort(arr):
    n = len(arr)
    gap = n // 2  # Initial increment is half the array length
    while gap > 0:
        # Traverse elements in each group
        for i in range(gap, n):
            temp = arr[i]  # Save current element to avoid overwriting
            j = i - gap    # Index of the previous element in the group
            # Shift larger elements in the group to the right
            while j >= 0 and arr[j] > temp:
                arr[j + gap] = arr[j]  # Shift right by one position
                j -= gap               # Continue comparing previous elements
            arr[j + gap] = temp        # Insert temp into the correct position
        gap = gap // 2  # Halve the increment to gradually reduce group size
    return arr

Code Explanation:
- n = len(arr): Get the array length to calculate the initial increment.
- gap = n // 2: The initial increment is half the array length (a common simple increment strategy).
- while gap > 0: Loop to process different increments until the increment is 0.
- for i in range(gap, n): Traverse elements starting from the gap-th element (each group’s elements).
- temp = arr[i]: Save the current element to prevent overwriting during shifting.
- j = i - gap: Calculate the index of the previous element in the same group.
- while j >= 0 and arr[j] > temp: Shift larger elements right until a smaller element is found or the start of the array is reached.
- arr[j + gap] = temp: Insert the saved element into its correct position.
- gap = gap // 2: Halve the increment to refine the grouping until the final pass with gap=1 (standard Insertion Sort).

Example (Using Array [5, 3, 8, 4, 2])¶

1. Initial Array: [5, 3, 8, 4, 2], n=5, initial increment gap=5//2=2.

2. Processing gap=2:
   - Grouping: Group 1 (indices 0, 2, 4: elements 5, 8, 2), Group 2 (indices 1, 3: elements 3, 4).
   - Group 1 Insertion Sort:

   • i=2 (element 8): j=0 (arr[0]=5 <=8), no shift. Array remains: [5,3,8,4,2].
   • i=4 (element 2): j=2 (arr[2]=8>2 → shift 8 to arr[4], array: [5,3,2,4,8]); j=0 (arr[0]=5>2 → shift 5 to arr[2], array: [5,3,5,4,8]); j=-2 (insert 2 at arr[0]). Group 1 sorted: [2,3,5,4,8].
   • Group 2 Insertion Sort:
   • i=3 (element 4): j=1 (arr[1]=3 <=4), no shift. Array remains: [2,3,5,4,8].

3. Processing gap=1 (increment halved to 1, equivalent to standard Insertion Sort):
   - i=1 (element 3): j=0 (arr[0]=2 <=3), no shift.
   - i=2 (element 5): j=1 (arr[1]=3 <=5), no shift.
   - i=3 (element 4): j=2 (arr[2]=5>4 → shift 5 to arr[3], array: [2,3,5,5,8]); j=1 (arr[1]=3 <=4 → insert 4 at arr[2]). Array becomes: [2,3,4,5,8].
   - i=4 (element 8): j=3 (arr[3]=5 <=8), no shift.

4. Final Result: [2, 3, 4, 5, 8].

Summary¶

• Time Complexity: Average O(n log n), worst case O(n²) (better than Insertion Sort).
• Space Complexity: O(1) (in-place sorting, only temporary variables used).
• Use Case: Effective for moderately sized arrays, especially when elements are unevenly distributed (grouping reduces shift operations).

By grouping and gradually reducing the increment, Shell Sort first “roughly sorts” the array and then “finely sorts” it, significantly improving the efficiency of Insertion Sort. It is a practical sorting algorithm.