Изменения
→Алгоритм построения за O(N)
В Кормене описываются мат. выкладки, доказывающие линейность карманной сортировки.
Что касается инверсий, то по сути дела в приведенной реализации происходит карманная сортировка в online режиме и вся мат.часть из Кормена подходит и под этот случай.
Хотя подсчет с помощью карманной сортировки выполняется за линейное время, но имеет очень большую константу т.ч. подсчет с помощью дерева Фенвика(которая выполняется за <tex>O(n*log(n))</tex>) часто работает быстрее рассматриваемого в данном случае.
Также следует учитывать с помощью какой сортировки вставлять элемент каждый раз. Если размер кармана не велик, то возможно лучше подойдет эффективная реализация квадратичной сортировки, иначе лучше использовать одну из быстрых сортировок. Известно, что маленькие массивы лучше сортировать квадратичной сортировкой. Но как узнать границу, после которой массив перестает быть маленьким? В общем случае эта верхняя граница находится между 32 и 40. У Тима Петерсона в Tim Sort'e это 64(правда это на Python'e).
== Алгоритм восстановления ==
