Quick Info

Category: Sorting
Time Complexity: Best: O(n log n)
Average: O(n log² n)
Worst: O(n²)
Space Complexity: O(1)
Stable: No
In-Place: Yes

Shell Sort

Sorting Medium

Description

Shell Sort is an optimization of insertion sort that allows the exchange of items that are far apart. The algorithm is named after its inventor, Donald Shell, who published it in 1959. Instead of comparing only adjacent elements, Shell Sort starts by comparing elements that are far apart and progressively reduces the gap between elements being compared.

History

Donald Shell

Shell Sort was invented by Donald L. Shell and published in 1959 in the journal Communications of the ACM. At the time, Shell was working at General Electric and developed this algorithm as a solution to improve the efficiency of insertion sort. The algorithm was groundbreaking because it was the first sorting algorithm to achieve sub-quadratic time complexity. Before Shell Sort, the best-known general-purpose sorting algorithms all had O(n²) time complexity. Shell's innovation was to allow the exchange of elements that are far apart, which helps to move items into their correct position faster than a simple adjacent exchange would. The original gap sequence proposed by Shell was n/2, but since then, many researchers have proposed and analyzed different gap sequences. Some notable sequences include Knuth's sequence (3ᵏ - 1) and Ciura's sequence (1, 4, 10, 23, 57, 132, 301, 701).

How It Works

  1. Gap Selection: Start with a large gap and reduce it over iterations
    • Initially gap = N/2
    • Each iteration: gap = gap/2
  2. Gapped Insertion Sort:
    • Compare elements that are gap positions apart
    • Swap them if they are in wrong order
    • Continue until gap becomes 1
  3. Final Pass: When gap = 1, perform regular insertion sort

Visualization

Click Start to begin visualization

Implementation


def shell_sort(arr):
    n = len(arr)
    gap = n // 2
    
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            
            # Shift elements that are gap positions apart
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            
            arr[j] = temp
        
        gap //= 2
    
    return arr

# Example usage
if __name__ == "__main__":
    arr = [64, 34, 25, 12, 22, 11, 90]
    print("Original array:", arr)
    sorted_arr = shell_sort(arr)
    print("Sorted array:", sorted_arr)
                                        

void shellSort(vector& arr) {
    int n = arr.size();
    
    // Start with a big gap, then reduce the gap
    for (int gap = n/2; gap > 0; gap /= 2) {
        // Do a gapped insertion sort for this gap size
        for (int i = gap; i < n; i++) {
            // Add arr[i] to the elements that have been gap sorted
            int temp = arr[i];
            int j;
            
            // Shift earlier gap-sorted elements up until the correct location for arr[i] is found
            for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
                arr[j] = arr[j - gap];
            }
            
            // Put temp (the original arr[i]) in its correct location
            arr[j] = temp;
        }
    }
}

// Example usage
int main() {
    vector arr = {64, 34, 25, 12, 22, 11, 90};
    cout << "Original array: ";
    for(int num : arr) cout << num << " ";
    
    shellSort(arr);
    
    cout << "\nSorted array: ";
    for(int num : arr) cout << num << " ";
    return 0;
}
                                        

public class ShellSort
{
    public static void Sort(int[] arr)
    {
        int n = arr.Length;
        
        // Start with a big gap, then reduce the gap
        for (int gap = n/2; gap > 0; gap /= 2)
        {
            // Do a gapped insertion sort for this gap size
            for (int i = gap; i < n; i++)
            {
                // Add arr[i] to the elements that have been gap sorted
                int temp = arr[i];
                int j;
                
                // Shift earlier gap-sorted elements up until the correct 
                // location for arr[i] is found
                for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
                {
                    arr[j] = arr[j - gap];
                }
                
                // Put temp (the original arr[i]) in its correct location
                arr[j] = temp;
            }
        }
    }
    
    // Example usage
    public static void Main(string[] args)
    {
        int[] arr = { 64, 34, 25, 12, 22, 11, 90 };
        Console.WriteLine("Original array: " + string.Join(" ", arr));
        
        Sort(arr);
        
        Console.WriteLine("Sorted array: " + string.Join(" ", arr));
    }
}

Gap Sequences

Different gap sequences can lead to different time complexities:

Sequence Name Sequence Time Complexity
Shell's Original N/2, N/4, ..., 1 O(n²)
Knuth's 1, 4, 13, 40, ... O(n^(3/2))
Ciura's 1, 4, 10, 23, 57, ... Unknown (Best empirical)

Advantages and Disadvantages

Advantages

  • In-place algorithm
  • Adaptive algorithm
  • Better than simple insertion sort
  • Works well for medium-sized arrays

Disadvantages

  • Not stable
  • Complex gap sequence selection
  • Performance depends on gap sequence
  • Not as efficient as quick sort or merge sort