Полю по которуму происхожит сортировка key,а остальные поля дополнительными. Поэтому сортировка происходит по ключу, но вмести с ключем перемещаються дополнительные данные. Различают внутреннию и внешнию сортировку. Внутрення сортировка предпологает, что данные находяться в оперативной памяти, в этом случае время доступа к элеменатам данных минимально. Внешняя сортировка подрузумевает расположение данных, на внешнем носителе. Время доступа в этом случаее значительно возрастает. И поэтому алгоритмы внешней сортировки работает на несколько порядков медленннее. Во многих случаеях оптимальным оказываеться вариант смешанной сортировки в этом случае данные, загружаються в ОП блоками, сортировка происходит в памяти и отсортированный блок вновь записываеться на внешне устройство. Загружаеться новый блок и т.д. Такой потход естественно требует выполнения операции слияние блоков отсортированных данных.
Для сортировки данных необходимо иметь одназначное трактование критерия сравнение данных. Для каждой пары данных. Не возникает сомнения какой из них будет предудышим а какой последующим. Методы сортировки «на месте»( без использования вспомогательных массивов) , можно разбить в соответствии с определяющими их принцапи на три котегории:
1) сортировка включением
2) сортировка выбором
3) сортировка обменом