Description

<integer_sort>- это быстрый шаблонный алгоритм гибридного радикса / сравнения, который при тестировании имеет тенденцию быть примерно на 50% до 2X быстрее, чем<std::sort>для больших тестов (>=100kB).

Performance: Worst-case performance is O(N * (lg(range)/s + s)) , so integer_sort is asymptotically faster than pure comparison-based algorithms. s is max_splits, which defaults to 11, so its worst-case with default settings for 32-bit integers is O(N * ((32/11) slow radix-based iterations fast comparison-based iterations).

Some performance plots of runtime vs. n and log(range) are provided:
windows_integer_sort
osx_integer_sort

	Warning
	Бросок исключения может привести к потере данных. Это также будет бросать, если бросит небольшой вектор размера, и в этом случае не будет потери данных. Недействительные аргументы вызывают неопределенное поведение.

	Note
	<spreadsort>Функция обеспечивает обертку, которая называет самый быстрый алгоритм сортировки, доступный для типа данных, что позволяет ускорить общее программирование.

Меньшая изO(N*log(N))сравнения иO(N*log(K/S + S))Операции в наихудшем случае, когда:

N<last>—<first>,

K - журнал диапазона в битах (32 для 32-битных целых чисел с использованием их полного диапазона),

S - постоянная, называемая max_splits, по умолчанию 11 (за исключением строк, где это журнал размера символа).