Внутренняя сортировка

Внутренняя сортировка (англ. internal sort) — разновидность алгоритмов сортировки или их реализаций, при которой оперативной памяти достаточно для помещения в неё сортируемого массива данных с произвольным доступом к любой ячейке и собственно для выполнения алгоритма. В этом случае сортировка происходит максимально быстро, т. к. время обращения к периферийным устройствам значительно выше чем к оперативной памяти. В зависимости от конкретного алгоритма и его реализации данные могут сортироваться в той же области памяти, либо использовать дополнительную оперативную память. Внутренняя сортировка является базовой для любого алгоритма внешней сортировки — отдельные части массива данных сортируются в оперативной памяти и с помощью специального алгоритма сцепляются в один массив, упорядоченный по ключу.

В современных архитектурах компьютеров и системных архитектурах широко применяется подкачка и кэширование памяти. Поэтому в большинстве случаев имеется возможность использовать внутреннюю сортировку даже для задач, в которых объём данных несколько превышает выделяемую процессу оперативную память. Однако, в последнем случае алгоритм сортировки должен хорошо сочетаться с применяемыми операционной системой алгоритмами кэширования и подкачки. В противном случае необходимо использовать подходящий алгоритм внешней сортировки.

Литература

• Дональд Э. Кнут Искусство программирования, том 2. Получисленные алгоритмы = The Art of Computer Programming, vol.2. Seminumerical Algorithms, 3-ed. — Вильямс, 2007. — С. 832. — ISBN 978-5-8459-0081-4
• Роберт Седжвик Фундаментальные алгоритмы на C. Анализ/Структуры данных/Сортировка/Поиск = Algorithms in C. Fundamentals/Data Structures/Sorting/Searching. — СПб.: ДиаСофтЮП, 2003. — С. 672. — ISBN 5-93772-081-4