What is Shell Sort?¶

Shell Sort is an improved version of Insertion Sort, also known as “diminishing increment sort”. It works by dividing the array into multiple subsequences, performing insertion sort on each subsequence, and then gradually reducing the increment until the increment is 1, completing the sorting of the entire array. The core idea is to allow elements in the array to “move” to their correct positions faster, thereby reducing the number of moves required in Insertion Sort.

Basic Idea of Shell Sort¶

1. Grouping: Select an increment (gap), and divide the array into several subsequences. Elements in each subsequence are spaced gap apart. For example, if the array length is 5 and the initial gap is 2, the subsequences are [arr[0], arr[2], arr[4]] and [arr[1], arr[3]].
2. Sort Subsequences: Perform direct insertion sort on each subsequence.
3. Reduce Increment: Reduce the increment gap (usually by halving, e.g., gap = gap / 2), and repeat steps 1 and 2 until gap = 1.
4. Final Sorting: When gap = 1, the entire array is already nearly sorted, and a single complete insertion sort is sufficient to finish the final sorting.

Why Reduce the Increment?¶

• Initial Large Increment: The array is divided into fewer subsequences, each of which is longer. Insertion sort has fewer moves in this case.
• Decreasing Increment: As the increment decreases, subsequences gradually merge, and the array becomes closer to being sorted, requiring only minimal moves to complete the final sort.

Example Sorting Process¶

Take the array [12, 34, 54, 2, 3] with initial length n=5 and initial gap 5/2=2:

1. First Grouping (gap=2):
   - Subsequence 1: [12, 54, 3] (indices 0, 2, 4)
   - Subsequence 2: [34, 2] (indices 1, 3)
   - After inserting and sorting each subsequence, the array becomes [12, 2, 54, 34, 3].

2. Reduce Increment (gap=1):
   - The array is now nearly sorted; perform a single insertion sort:

   • When processing 3, compare with previous elements 54, 34, 12, and insert at index 0. The array becomes [3, 2, 12, 34, 54].
   • When processing 2, compare with 3 and insert at index 1. The array becomes [2, 3, 12, 34, 54].

Final sorted result: [2, 3, 12, 34, 54].

C++ Code Implementation¶

#include <iostream>
using namespace std;

// Shell Sort function
void shellSort(int arr[], int n) {
    // Start with a large gap, then reduce the gap
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // Perform insertion sort for elements at each gap interval
        for (int i = gap; i < n; i++) {
            int temp = arr[i]; // Current element to be inserted
            int j;
            // Shift earlier gap-sorted elements up until the correct position for arr[i] is found
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            arr[j] = temp; // Insert the temp element
        }
    }
}

// Function to print the array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {12, 34, 54, 2, 3};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Array before sorting: ";
    printArray(arr, n);

    shellSort(arr, n);

    cout << "Array after sorting: ";
    printArray(arr, n);

    return 0;
}

Code Explanation¶

1. Outer Loop (Gap Control): The gap starts at n/2 and is halved each iteration until gap=0.
2. Middle Loop (Grouped Insertion Sort): For each gap, iterate through the array starting from index gap, treating each element arr[i] as a temporary element to be inserted.
3. Inner Loop (Element Shifting): Compare the temporary element with previous elements in its subsequence (spaced gap apart). If a previous element is larger, shift it forward by gap positions. Continue until the correct position for the temporary element is found, then insert it.

Time Complexity and Space Complexity¶

• Time Complexity: Average O(n^1.3) (depends on gap selection), Worst O(n^2).
• Space Complexity: O(1) (only temporary variable temp is used).
• Stability: Unstable (grouped insertion sort may alter the relative order of equal elements).

Summary¶

By grouping elements and reducing the increment, Shell Sort effectively reduces the number of moves required in Insertion Sort. It is more efficient than standard Insertion Sort for larger arrays. Beginners can master its implementation by understanding the core logic: “Group → Sort → Reduce Increment → Final Sort”.