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

Array.Sort() в C# использует алгоритм разумной сортировки (introsort) следующим образом:
Если размер раздела меньше 16 элементов, он использует insertion sort алгоритм.
Если количество секций превышает 2 * log(N), где N диапазон входного массива, он использует Heapsort алгоритм.
В противном случае он использует Quicksort алгоритм.
У меня такой вопрос: как этот алгоритм высчитывает количество секций в массиве? Было бы глупо предположить, что встроенная сортировка сначала высчитывает на сколько секций квиксорт разделит этот массив, а потом уже выбирает алгоритм.
Может быть есть какая-то формула?

Ответ

Я думаю, что понятие "количество секций в массиве" здесь появилось вследствие какого-то недоразумения - возможно, кривой перевод.
Интросорт использует быструю сортировку, которая выполняет разделение массива (partition) на части по выбранному опорному элементу (pivot). Вот если массив особо гнусный и опоры выбираются неудачно, то этих самых разделений будет слишком много. Интросорт следит за этим (глубина), и переключается на сортировку кучей. Для идеального случая глубина log2(n). Каков критерий глубины для переключения - зависит от конкретной реализации. Вот пример:
The GNU Standard C++ library is similar: uses introsort with a maximum depth of 2×log2 n
И опять мы видим использование кривого перевода - log это логарифм, а не журнал