====================================================================
> 6. Описание и исходник ShellSort (сортировка Шелла)
====================================================================

Этот алгоритм - модификация сортировки простыми вставками.

Идея, например, в случае 16 чисел n1 ... n16 такова:

Вначале сортируем простыми вставками каждые 8 групп из 2-х элементов 
(n1, n9), (n2, n10), ... , (n8, n16).

Потом сортируем каждую из четырех групп по 4 элемента (n1, n5, n9, n13),
 ..., (n4, n8, n12, n16). Далее сортируем 2 группы по 8 элементов, 
начиная с (n1, n3, n5, n7, n9, n11, n13, n15).
А в конце сортируем вставками все 16 элементов.

Очевидно, лишь последняя сортировка необходима, 
чтобы расположить все элементы по своим местам. 
Так зачем нужны остальные ? 

Hа самом деле они продвигают элементы максимально близко
к соответствующим позициям, так что в последней стадии число
перемещений будет весьма невелико. Они и так почти рассортированы.

Были проведены многочисленные исследования по вопросу, 
какова должна быть последовательность расстояний между сортируемыми 
элементами в зависимости от прохода (инкремент). 

В конце мы все равно сортируем весь массив вставками, так
что, очевидно, любая последовательность подойдет. Hабор
 ..., 8, 4, 2, 1 - неплохой выбор, особенно, 
когда N - степень двойки. Hо гораздо лучше будет взять

( 3k - 1 )/2, ..., 40, 13, 4, 1
Ее можно вычислить рекуррентно:

i_1 = 1, i_k+1 = 3i_k + 1, k = 1, 2, ...
При этой последовательности количество операций даже 
в наихудшем случае - порядка N^3/2.

Для случайной последовательности при N < 60000 
количество операций, приблизительно, N^1.25, 
однако уже при N > 50 QuickSort быстрее.

Исходник на Си.
void shell(unsigned long n, float a[])
{
    unsigned long i, j, inc; 
	float v; 
	inc=1;                         // начальный инкремент 
	do {
	    inc *=3; 
		inc++; 
	} while (inc <= n); 
	do {                           // Цикл частичных сортировок
	    inc /=3; 
		// Внутренний цикл простых вставок
	    for (i=inc+1; i<=n; i++) {
		    v=a[i]; 
			j=i; 
			while ( a[j-inc] > v) {
			    a[j] = a[j-inc]; 
				j -= inc; 
				if ( j <= inc ) break; 
			}
			a[j]=v; 
		}
	} while ( inc > 1 ); 
}