Shell Sort

ShellSort is mainly a variation of Insertion Sort.  
In insertion sort, we move elements only one position ahead. When an element has to be moved far ahead, many movements are involved. 
The idea of shellSort is to allow exchange of far items.


int shellSort(int arr[], int n)
{
    // 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++)
        {
            int temp = arr[i];
            for (int j = i; j >= gap && arr[j - gap] > temp; j -= gap)
                arr[j] = arr[j - gap];
             
            arr[j] = temp;
        }
    }
}
Some sorting algorithms are stable by nature like Insertion sort, Merge Sort, Bubble Sort, etc. 
And some sorting algorithms are not, like Heap Sort, Quick Sort, etc.