Shell Sort

Shell Sort is a sorting algorithm in which the items will be converted into nearly sorted list and sort by using insertion sort.

Algorithm:

The algorithm will sort every Ath item in the list and Bth item in the list(A>B).In this process, the list will be changed into nearly sorted list. After that, we can use the insertion sort.(see Insertion Sort). Or it can be explained by deviding the list into columns.

Psuedocode:

void shellsort (int[] a, int n)
{
    int i, j, k, h, v;
    int[] cols = {1391376, 463792, 198768, 86961, 33936, 13776, 4592,
                    1968, 861, 336, 112, 48, 21, 7, 3, 1}
    for (k=0; k<16; k++)
    {
        h=cols[k];
        for (i=h; i<n; i++)
        {
            v=a[i];
            j=i;
            while (j>=h && a[j-h]>v)
            {
                a[j]=a[j-h];
                j=j-h;
            }
            a[j]=v;
        }
    }
}

Source:
http://en.wikipedia.org/wiki/Shell_sort
http://www.sorting-algorithms.com/shell-sort
http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/shell/shellen.htm