Однією з найбільш поширених операцій обробки масивів є їх упорядкування, або сортування. Упорядкування масиву — це зміна порядку розташування його елементів за певним критерієм. Наприклад, числовий масив можна упорядкувати за зростанням значень його елементів або за їх спаданням, а масив рядків можна У відсортувати в алфавітному порядку. Найчастіше сортування масиву здійснюється з метою полегшення подальшого пошуку.
Відомо багато методів сортування масиву, що відрізняються швидкодією й обсягом оперативної пам'яті, яка при цьому використовується. Серед цих методів можна вирізнити методи внутрішнього та зовнішнього сортування. Методи внутрішнього сортування не передбачають використання допоміжних масивів. Ці методи застосовують до масивів, що повністю розташовані в оперативній пам'яті. Методи зовнішнього сортування застосовують до великих масивів даних, які зберігаються на зовнішніх носіях. У цьому розділі розглянемо методи внутрішнього сортування масиву, обмежуючись задачею сортування за зростанням. Методи внутрішнього сортування прийнято поділяти на дві групи: елементарні (прямі) та удосконалені методи.
Найбільш відомими елементарними методами сортування масиву є:
♦ сортування вставкою (включенням);
♦ сортування вибором;
♦ сортування обміном (бульбашкове сортування).
З удосконалених методів сортування найчастіше використовуються такі:
♦ швидке сортування, або метод Хоара;
♦ сортування включенням зі спадним приростом, або метод Шелла;
♦ сортування за допомогою дерева, або пірамідальне сортування;
♦ сортування методом злиття.
Нижче буде розглянуто всі три вищезгаданих елементарних методи сортування та два удосконалених — метод Хоара й метод злиття.
