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