СОРТИРОВКА ДАННЫХ
— обработка информации, в результате которой элементы ее (записи) располагаются в определенной последовательности в зависимости от значения некоторых признаков элементов, называемых ключевыми.
Наиболее распространенным видом С. д. является упорядочение массива — расположение записей сортируемого массива данных в порядке монотонного изменения значения ключевого признака. С. д. позволяет сократить в десятки раз продолжительность решения задач, связанных с обработкой больших массивов записей. Такое ускорение происходит за счет сокращения времени поиска записей с определенными значениями ключевых признаков. Упорядочение осуществляется в процессе многократного просмотра Исходного массива.
С. д., размещенных внутри оперативного запоминающего устройства (ОЗУ) с произвольной выборкой наз. внутренней сортировкой. С. д., объем которых значительно превышает емкость ОЗУ, производится с использованием внешних запоминающих устройств (ленты магнитные, диски магнитные и т. п.), и наз. внешней сортировкой. Важнейшей Характеристикой процесса С. д. является его производительность, определяемая временем, затрачиваемым на выполнение сортировки. Другой важной характеристикой процесса С. д. является объем памяти, необходимой для выполнения сортировки (см. Память ЦВМ). Производительность и потребность в памяти зависят от применяемого метода сортировки.
Существующие методы внутренней сортировки можно разделить на два класса: 1) методы, для выполнения которых достаточно минимального объема памяти, равного объему сортируемого массива записей (метод Шелла, P-операторный, вставки и др.); 2) методы, требующие выполнения минимального (или близкого к минимальному) времени сортировки (методы слияния, сортировки по шкале признаков, древовидной сортировки, выбора и замены, обмена по основанию системы счисления и др.).
В существующих методах внешней сортировки время обращения к внешней памяти занимает значительную часть (до 90%) общего времени сортировки. Поэтому важной целью методов внешней С. д. является минимизация количества просмотров сортируемого массива, записанного во внешней памяти, используемой, как правило, в режиме последовательной выборки. Большинство известных методов внешней сортировки (балансный, каскадный, многофазный и др.) состоят из нескольких этапов. На 1-м этапе записи сортируемого массива считываются группами с входной магнитной ленты в ОЗУ и упорядочиваются там с помощью методов внутренней сортировки, а затем записываются на выходную магнитную ленту. В результате 1-го этапа сортируемый массив записей оказывается разбитым на начальные группы, каждая из которых упорядочена. На 2-м этапе производится объединение (слияние) по 
упорядоченных групп записей в общую упорядоченную группу. В результате к-во записей, входящих в одну упорядоченную группу, увеличивается в 
раз. На 3-м этапе производится слияние по 
укрупненных групп записей в новые упорядоченные группы и т. д. до тех пор, пока не сформируется одна упорядоченная группа, включающая все записи исходного массива. При 
для выполнения упорядочения требуется произвести не более 
просмотров исходного массива, где N - к-во начальных групп, полученных на 1-м этапе.
Процесс слияния упорядоченных групп происходит так. Группы Записей вводятся в ОЗУ (целиком или частями). Рассматриваются признаки первых записей каждой группы. Из них выбирается наименьший (при упорядочении по возрастанию), и запись, которой принадлежит этот признак, включается в формируемую группу. Взамен в рассмотрение вводится признак следующей записи из той группы, которой принадлежала запись, включенная в формируемую группу, снова выбирается наименьший из рассматриваемых признаков и т. д. до тех пор, пока в формируемую группу не будут включены все записи объединяемых групп. К-во просмотров сортируемого массива уменьшается с ростом 
, а время сортировки записей при каждом просмотре увеличивается. Поэтому существует такое оптимальное по, которое минимизирует машинное время, затрачиваемое на упорядочение данного массива. Величина по тем больше, чем выше быстродействие вычисл. машины и чем меньше скорость обмена с внешней памятью.
Помимо слияния, для С. д. применяется и метод разделения, при выполнении которого записи массива разделяются на группы в зависимости от значения некоторого разряда кода ключевого признака. Упорядочение массива заканчивается после разделения по всем разрядам кода ключевого признака, начиная с младшего. Разделение применяется преимущественно при упорядочении массивов перфокарт на электромёх. устр-вах.
С целью сокращения затрат на многократные пересылки элемента в процессе С. д. в случаях,
когда размер сортируемых записей значительно превосходит размер их ключевых признаков, С. д. производят с помощью вспомогательного массива т. н. слов-признаков. Каждое слово-признак содержит некоторый ключевой признак и адрес расположения в памяти элемента массива, обладающего этим признаком. После сортировки массива слов-признаков производится однократная перезапись элементов сортируемого массива на нужные места в соответствии с адресами слов-признаков. Применение такого метода целесообразно в ЗУ с произвольной и квазипроизвольной выборкой (магнитные диски и т. п.).
Частным видом С. д. является группировка элементов массива, в результате выполнения которой все элементы, обладающие одинаковыми значениями ключевого признака, в массиве располагаются рядом.
Лит.: Алферова 3. В., Волович М. А. Сортировка информации с помощью электронных вычислительных машин. М., 1965; Gotlieb С. С. Sorting on computers. «Communications of the Association for Computing Machinery», 1963, v. 6, № 5.
Л. И. Шолмое.
