Під сортуванням розуміють процес розміщення об'єктів деякої множини у заданому порядку з метою полегшення подальшого пошуку елементів цієї множини з метою обробки та використання.
Розрізнюють сортування масивів (внутрішнє сортування) та файлів (зовнішне сортування), у залежності від того, де знаходиться елементи що сортуються - у внутрішній пам'яті ЕОМ або на зовнішніх носіях.
Якщо елементи позначити через
a1, a2, . . . , an-1, an,
то сортування означає перестановку іх у такому порядку
a i1, a i2, . . . , a in-1, a in,
що задана функція впорядкування f(x) буде нестрого монотонною на цій послідовності:
f(a i1) Ј f(a i2) Ј . . . Ј f(a in-1) Ј f(a in).
Значення f(ai) називаються ключем елементу ai. Так само, як у алгоритмах пошуку, будемо вважати, що дані мають структурований тип:
type
Item = record
key : integer;
rest = record
{ ... the rest}
end;
end;
Алгоритм сортування називається сталим (stable (англ.), устойчивым (рос.)), якщо у відсортованому масиві він не змінює порядку розташування елеиентів.
Ефективність методів сортування будемо визначати двома параметрами:
C - кількістю порівнянь (від compare);
M - кількістю пересилань елементів (від move).
Ці параметри будемо визначати у залежності від n - кількості елементів множини (масиву або файлу), що сортується.
При цьому окремо розглянемо алгоритми сортування масивів та окремо - файлів.
При сортуванні масивів вважається, що масив увесь розміщено у пам'яті, тому не розглядаються алгоритми, що пересилають елементи повністю у інший масив, на який може не вистачити пам'яті. З іншого боку, для сортування масиву важливим є зменшення як C так і M, особливо для значних n.
При сортуванні файлів ми фактично маємо доступ лише до одного поточного елементу файлу, а решту елементів можемо переглядати лише послідовно. Тому для таких алгоритмів обов'язковим є саме переписування файлу на інший зовнішній носій. З іншого боку, істотним є для сортування файлів зменшення лише M - кількості пересилань елементів, бо кожне пересилання вимагає запису або читання (обміну) з зовнішнім носієм, що є довгою операцією. Кількість порівнянь C не має суттєвого значення.