Обсуждение:PSRS-сортировка

Оптимизации

Бинарные вставки

Так как в среднем количество сравнений для [math]j[/math]-го элемента равно [math]j/2[/math], следовательно общее количество сравнений приблизительно [math]\frac {(1+2+3+...+N)}{2} \approx N^2/4[/math], но это очень много даже при малых [math]N[/math]. Суть этого заключается в том, что поиск позиции для вставки [math]j[/math]-го элемента осуществляется бинарным поиском, вследствие чего количество сравнений для [math]N[/math] элементов [math]N \cdot \log_{2} N[/math].Количество сравнений заметно уменьшилось, но для того, чтобы поставить [math]R_j[/math] элемент на [math]i[/math]-тое место, всё ещё необходимо переместить [math]j-i[/math] элементов.Что касается константы [math]C[/math], то [math]C \cdot N \cdot (N/4+log_{2} N) \approx N^2/4[/math], следовательно [math]C=1/4[/math].

Двухпутевые вставки

Суть этого метода в том, что вместо отсортированной части массива мы используем область вывода. Первый элемент помещается в середину области вывода, а место для последующих элементов освобождается потём сдвига элементов влево или вправо туда, куда выгоднее. Пример для набора элементов 5 7 3 4 6

     5
     5 7
   3 5 7
 3 4 5 7
 3 4 5 6 7 

Как мы видим в этом примере понадобилось сдвинуть всего 3 элемента. Что касается константы [math]C[/math], то [math]C \cdot N \cdot (N/8+log_{2} N) \approx N^2/8[/math], следовательно [math]C=1/8[/math].