Использование оперативной памяти при сортировке

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

Так, если требуется рассортировать элементов информации, каждый из которых занимает по т ячеек, и записать их в ячеек памяти, необходимо выделить место для адресов, которые и будут переставлены (в соответствии со значениями ключей) в том порядке, в каком должны быть расположены сами элементы. Описанный метод обработки информации может быть использован и при работе с магнитным барабаном, так как время выборки у него сравнительно невелико.
Методы сортировки
Существует два основных метода сортировки:
1. Сортировка по числовым ключам.
2. Сортировка объединением.
При этом методе ключ состоит из цифры (или группы цифр), по значениям которых в возрастающем порядке должна быть упорядочена информация. Этот метод обычно используется на счетно-аналитических машинах, где информация прогоняется через сортировочное устройство один раз для каждой цифры в заданном ключе, а карты собираются в один из десяти приемных устройств (в этих машинах используется десятичная система счисления), при каждом прогоне.

Источник: delete-it