The **shell sort algorithm** extends the *[insertion sort](https://www.educative.io/answers/what-is-insertion-sort-in-java) algorithm* and is very efficient in sorting widely unsorted arrays. The array is divided into sub-arrays and then insertion sort is applied. The algorithm is:

1. Calculate the value of the ​gap (*formula given in the illustration below*).
2. Divide the array into these sub-arrays.
3. Apply the insertion sort.
4. Repeat this process until the complete list is sorted. 

>Note: This algorithm will sort in *ascending* order.

The algorithm is illustrated below: 

#include <iostream>
using namespace std;

//Shell sort.
void ShellSort(int arr[], int n)
{
	int i, j, k, temp;
	// Gap (i) is calculated in this loop.
	for( i = n/2; i > 0; i = i/2)
	{
		for(j = i; j < n; j++)
		{
			for(k = j-i; k >= 0; k = k-i)
			{
				// Higher index value is greater than lower index,
        // then no swapping required.
				if(arr[k+i] >= arr[k])
				    break;
				else
				{
          // swap the elements.
					temp = arr[k];
					arr[k] = arr[k+i];
					arr[k+i] = temp;
				}
			}
		}
	}
}

// Driver Program
int main()
{	
	// sample array.
  int arr[] = {13, 10, 11, 2, 5, 8, 15};
  int n= 7;

  // Printing the unsorted array.
	cout<<"\nUnsorted array: ";
	for (int i = 0; i < n; i++)
		 cout<<arr[i]<< ",";
 
	ShellSort(arr, n);
 
	// Printing the sorted array.
	cout<<"\nAfter Shell sort, the array is: ";
	for (int i = 0; i < n; i++)
		 cout<<arr[i]<< ",";
 
	return 0;
}

import java.util.*; 

public class main   
{  
    //Shell sort.
    public static void shellsort(int[] arr, int num)    
    {    
      int i, j, k, tmp;
       // Gap (i) is calculated in this loop.   
      for (i = num / 2; i> 0; i = i / 2)    
      {    
          for (j = i; j<num; j++)    
          {    
            for(k = j - i; k>= 0; k = k - i)    
            {  
              // Higher index value is greater than lower index,
              // then no swapping required.  
              if (arr[k+i] >= arr[k])    
                break;    
              else  
                {  
                  // swap the elements.  
                  tmp = arr[k];    
                  arr[k] = arr[k+i];    
                  arr[k+i] = tmp;    
            }   }    
          }    
      }    
    }    
    
    // Driver Program
    public static void main(String[] arguments)   
    {    
      // Sample array
      int[] arr= {13, 10, 11, 2, 5, 8, 15};    
      int k, n; 

      n = 7;

      System.out.println("\n Unsorted array is: ");    
      for (k = 0; k < n; k++){   
        System.out.println(arr[k]);    
      }

      shellsort(arr, n);

      System.out.println("\n After sorting it using Shell sort: ");    
      for (k = 0; k < n; k++){   
        System.out.println(arr[k]);    
      }    
   } 
} 

What is a shell sort?

Code