Эту статью я бы хотел посвятить еще одному замечательному алгоритму сортировки, носящему имя Дональда Шелла.
Не секрет, что сортировка Шелла зачастую работает медленнее, чем быстрая сортировка (сортировка Хоара), которую я рассматривал в одной из предыдущих статей. Однако, быстрая сортировка быстро замедляется до квадратичной сложности при неудачном наборе данных, что является худшим результатом, чем худшее время для сортировки Шелла.

При сортировке мы сравниваем и сортируем элементы в массиве, отстоящие друг от друга на n ячеек. Далее n уменьшается и процедура повторяется снова с обновленным значением n. Так до тех пор, пока n не уменьшится до 1.

Особое внимание нужно уделить выбору набора расстояний n. Сам Дональд Шелл предложил последовательность N1 = L/2, Ni = Ni-1/2, Nk = 1. Такая последовательность в худшем случае обеспечивает квадратичную сложность.
Улучшение этой последовательности разработал Роберт Седжвик (кстати, автор отличной книжки по алгоритмам) : Ni = 9*2^i — 9*2^(i/2) + 1. При этом требуется остановка на значении inc[s-1], если 3*inc[s] > size, где size — размер сортируемого массива. В худшем случае сложность будет порядка 4/3.
Для массивов до 4000 элементов лучшей считается последовательность Циура : {1, 4, 10, 23, 57, 132, 301, 701, 1750}.

После выбора последовательности расстояний можно приступить к реализации.
Как и всегда, в функцию сортируемый массив будем передавать по ссылке. Для примера я буду уменьшать шаг вдвое на каждой итерации.

function(&$a){
	$sort_length = count($a) - 1;
	$step = ceil(($sort_length + 1)/2);

	do{
		// тело цикла

		// конец цикла
		$step = $step / 2;
	}
	while($step > 0)
}

В теле цикла мы собираем подмассив значений, ключи которых отстоят друг от друга на шаг, указанный в цикле, и сортируем их простой вставкой.

	// тело цикла

	$i = ceil($step);
	   do
	   {
	     $j=$i-$step;
	     $c=1;
	     do
	     {
	       if($a[$j]<=$a[$j+$step])
	       {
		  	$c=0;
	       }
	       else
		   {
		      $tmp=$a[$j];
		      $a[$j]=$a[$j+$step];
		      $a[$j+$step]=$tmp;
		   }
		$j=$j-1;
	     }
	     while($j>=0 && ($c==1));
	      $i = $i+1;
	    }
	    while($i<=$sort_length);

	    // конец цикла

Результат сортировки таков можно посмотреть здесь:

Демо-пример

И как всегда - ссылочка на гитхаб

За сим на сегодня все! Безошибочного Вам кода!