[Algorithm] Shell sort

Shell sort

• Start by sorting pairs of elements far apart from each other, then reduce the gap between elements to be compared.
• Generalization of insertion sort
  • Sort every k-th elements by considering k interleaved lists.
  • Reduce the size of k by 1.

• This is similar to insertion sort, but considers the gap between elements.
  • When the gap is one, it is same as insertion sort.

void IncInsertionSort(int* list, int first, int last, int k)
{
	int i, j, key;
    // Sort every k-th element
    for (i = first + k; i < last; i = i + k)
    {
    	key = list[i]; // Choose the i-th element.
        // If the j-th element is greater than key.
        // move to the next position with k interval.
        for(j = i - k; j >= first && key < list[j]; j = j - k)
        	list[j + k] = list[j];
        list[j + k] = key;
    }
}

void ShellSort(Data* list, int n)
{
	// Sort every k-th element by reducing from n/2 to 1.
    for (int k = n / 2; k > 0; k /= 2)
    {
    	// Choose the k-th element as the odd.
        if ((k % 2) == 0) k++
        for(int i = 0; i < k; i++)
        	IncInsertionSort(list, i, n, k);
    }
}

• Time complexity
  • Average case: 𝑂(𝑛log𝑛)
  • Worst case: 𝑂(𝑛^2)
• Shell sort is not stable.