Сортування злиттям. У загальній постановці завдання сортування ставиться таким чином

У загальній постановці завдання сортування ставиться таким чином. Є послідовність однотипних записів, одне з полів яких вибране як ключове (далі ми називатимемо його ключем сортування). Тип даних ключа повинен включати операції порівняння («=», «>», «<», «>=» і «<=»). Завданням сортування є перетворення початкової послідовності в послідовність, що містить ті самі записи, але у порядку зростання (або спадання) значень ключа. Метод сортування називається стійким, якщо при його застосуванні не змінюється відносне положення записів із рівними значеннями ключа.

Розрізняють сортування масивів записів, розташованих в основній пам'яті (внутрішнє сортування), і сортування файлів, що зберігаються в зовнішній пам'яті і не вміщуються повністю в основній пам'яті (зовнішнє сортування). Для внутрішнього і зовнішнього сортування потрібні істотно різні методи.

Природною умовою, що висувається до будь-якого методу внутрішнього сортування є те, що ці методи не повинні вимагати додаткової пам'яті: всі перестановки з метою впорядкування елементів масиву мають вироблятися в межах того ж масиву. Мірою ефективності алгоритму внутрішнього сортування є кількість необхідних порівнянь значень ключа (С) і кількість перестановок елементів (М).

Зазначимо, що оскільки сортування засноване тільки на значеннях ключа і ніяк не зачіпає поля записів, що залишилися, можна говорити про сортування масивів ключів.