The shell sort algorithm is an extended version of an insertion sort. Shell sort improves the average time complexity of insertion sort

This is a comparison-based and in-place sorting algorithm, similar to insertion sort. Shell sort is effective for medium-sized data sets.

In insertion sort, at a time elements can only be moved forward by one position. It takes many movements to move an element to a far-away position, which increases the algorithm’s execution time.

Shell sort overcomes this problem of insertion sort. It makes it possible to move and swap distant elements as well.

The algorithm first sorts elements that are far from each other, and then it reduces their distance from each other. This distance is called an interval.

Here is the Knuth’s formula for calculating intervals –

h = h * 3 + 1
where −
   h is an interval with an initial value of 1

Time Complexity

Best Case O(n log n): It occurs when there is no sorting needed, i.e. the array is already sorted.

Average Case O(n log (n)²): The array elements are in a jumbled order that is not properly ascending and descending.

Worst Case O(n²): This occurs when the array elements need to be sorted in reverse order.

Space Complexity

The space complexity of shell sort is O (1).

Example

C Program

#include <stdio.h>    
/* function to implement shellSort */  
int shell_sort(int a[], int n) {  
    /* Rearrange the array elements at n/2, n/4, ..., 1 intervals */
    for (int interval = n/2; interval > 0; interval /= 2) {  
        for (int i = interval; i < n; i += 1) {  
            /* store a[i] to the variable temp and make the ith position empty */  
            int temp = a[i];  
            int j;        
            for (j = i; j >= interval && a[j - interval] > temp; j -= interval)  
                a[j] = a[j - interval];  
              
            // put temp (the original a[i]) in its correct position 
            a[j] = temp;  
        }  
    }  
    return 0;  
}  

/* function to print the array elements */  
void print(int a[], int n) {  
    for (int i = 0; i < n; i++)  
        printf("%d ", a[i]);  
}    

int main() {  
    int a[] = { 42, 12, 17, 25, 40, 8, 42, 33, 31 };  
    int n = sizeof(a) / sizeof(a[0]);  
    printf("Before sorting array elements are - n");  
    print(a, n);  
    shell_sort(a, n);  
    printf("nAfter applying shell sort, the array elements are - n");    
    print(a, n);  
    return 0;  
}  

Java Program

class ShellSort {  
    /* function to implement shellSort */  
    static void shellSort(int a[], int n) {  
        /* Rearrange the array elements at n/2, n/4, ..., 1 intervals */  
        for (int interval = n/2; interval > 0; interval /= 2) {  
            for (int i = interval; i < n; i += 1) {  
                /* store a[i] to the variable temp and make the ith position empty */  
                int temp = a[i];  
                int j;        
                for (j = i; j >= interval && a[j - interval] >   
    temp; j -= interval)  
                    a[j] = a[j - interval];  
                /* put temp (the original a[i]) in its correct  
    position */  
                a[j] = temp;  
            }  
        }  
    }  
    
    /* function to print the array elements */  
    static void print(int a[], int n) {  
        for (int i = 0; i < n; i++)  
            System.out.print(a[i] + " ");  
    }
    
    public static void main(String args[]) {  
        int a[] = { 42, 12, 17, 25, 40, 8, 42, 33, 31 };
        int n = a.length;  
        System.out.print("Before sorting array elements are - n");
        print(a, n);  
        
        shellSort(a, n);  
        System.out.print("nAfter applying shell sort, the array elements are - n");    
        print(a, n);  
    }      
}