Как высчитывается количество секций (partitions) в массиве

#c_sharp #net #сортировка

Array.Sort() в C# использует алгоритм разумной сортировки (introsort) следующим образом:

Если размер раздела меньше 16 элементов, он использует insertion sort алгоритм.

Если количество секций превышает 2 * log(N), где N диапазон входного массива, он
использует Heapsort алгоритм.

В противном случае он использует Quicksort алгоритм.

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

Может быть есть какая-то формула?
    

Ответы

Ответ 1

Я думаю, что понятие "количество секций в массиве" здесь появилось вследствие какого-то
недоразумения - возможно, кривой перевод.

Интросорт использует быструю сортировку, которая выполняет разделение массива (partition)
на части по выбранному опорному элементу (pivot). Вот если массив особо гнусный и опоры
выбираются неудачно, то этих самых разделений будет слишком много. Интросорт следит
за этим (глубина), и переключается на сортировку кучей. Для идеального случая глубина
log2(n). Каков критерий глубины для переключения - зависит от конкретной реализации.
Вот пример:


  The GNU Standard C++ library is similar: uses introsort with a maximum
  depth of 2×log2 n


И опять мы видим использование кривого перевода - log это логарифм, а не журнал