); тепер сортується хвіст списку, виключивши з розгляду вже відсортовані елементи;
шейкер: береться до уваги той факт, що від останньої перестановки до кінця (початку) масиву знаходяться відсортовані елементи, тому перегляд здійснюється не до кінця (початку) масиву, а до конкретної позиції. Отже необхідно запам'ятовувати індекс останньої перестановки. На наступному кроці циклу почнемо перегляд з останньою перестановки. Перегляд масиву здійснюється зліва направо (встановлюється права межа). Потім справа наліво (встановлюється ліва межа). Перегляд масиву здійснюється доти, поки всі елементи не встануть в порядку зростання (спадання);
шелла: спочатку порівнюються і сортуються між собою значення, віддалені один від одного на деякій відстані d. Після цього процедура повторюється для деяких менших значень d, а завершується сортування Шелла упорядкуванням елементів при d=1 (тобто звичайної сортування вставками);
швидка: вибрати з масиву елемент, званий опорним, це може бути будь-який з елементів масиву; cравніть всі інші елементи з опорним і переставити їх у масиві так, щоб розбити масив на три безперервних відрізка, наступні один за одним - «менші опорного», «рівні» та «великі»; для відрізків «менших» і «великих» значень виконати рекурсивно ту ж послідовність операцій, якщо довжина відрізка більше одиниці;
Гном: алгоритм, схожий на сортування вставками, але на відміну від останньої перед вставкою на потрібне місце відбувається серія обмінів, як у сортуванні бульбашкою;
злиттям: сортируемое масив розбивається на дві частини приблизно однакового розміру; кожна з одержані частин сортується окремо, наприклад - тим же самим алгоритмом; дві впорядкованих масиву половинного розміру з'єднуються в один;
двійковим деревом: універсальний алгоритм сортування, що полягає в побудові двійкового дерева пошуку по ключах масиву, з наступною збіркою результуючого масиву шляхом обходу вузлів побудованого дерева в необхідному порядку проходження ключів;
timSort: за спеціальним алгоритмом вхідний масив поділяється на подмассіви; кожен подмассів сортується сортуванням вставками; відсортовані подмассіви збираються в єдиний масив за допомогою модифікованої сортування злиттям;
підрахунком: підраховуємо, скільки разів в масиві зустрічається кожне значення, і заповнюємо масив підрахованими елементами у відповідних кількостях;
блочний: алгоритм сортування, в якому сортовані елементи розподіляються між кінцевим числом окремих блоків так, щоб всі елементи в кожному наступному по порядку блоці були завжди більше (або менше), ніж у попередньому. Кожен блок потім сортується окремо, або рекурсивно тим же методом, або іншим. Потім елементи поміщаються назад в масив;
гребінцем: основна ідея «гребінця» в тому, щоб спочатку брати досить велику відстань між порівнюваними елементами і в міру упорядкування масиву звужувати це відстань аж до мінімального;
пірамідальна: використовується Сортувальне дерево. Шикуються елементи масиву у вигляді сортують дерева. Видаляються елементи з кореня по одному за раз, і дерево перебудовується;
поразрядное: числа упорядковано за розрядами. Існує два варіанти least significant digit (LSD) і most significant digit (MSD). При LSD сортуванню, спочатку упорядковано молодші розряди, потім старші. При MSD сортуванні все навпаки;
дурна: йде пошук від початку масиву, поточний елемент порівнюється з наступним, якщо наступний менше, то проводиться обмін і повернення в початок циклу.
Основні алгоритми зовнішньої сортування, використовувані в програмі:
природна сортування (метод природного злиття): у разі простого злиття часткова впорядкованість сортируемих даних не дає ніякої переваги. Це пояснюється тим, що на кожному проході зливаються серії фіксованої довжини. При природному злитті довжина серій не обмежується, а визначається кількістю елементів у вже впорядкованих підпослідовність, що виділяються на кожному проході. Алгоритм: вихідний файл f розбивається на два допоміжних файлу f1 і f2. Допоміжні файли f1 і f2 зливаються в файл f, при цьому серії утворюють впорядковані послідовності. Отриманий файл f знову обробляється, як зазначено в кроках 1 і 2. Повторюючи кроки, зливаємо впорядковані серії до тих пір, поки не буде впорядкований цілком весь файл;
сортування методом двоколійному збалансованого злиття: алгоритм сортування простим злиття є найпростішим алгоритмом зовнішньої сортування, заснований на процедурі злиття серією. У даному алгоритмі довжина серій фіксується на кожному кроці. У вихідному файлі всі серії мають довжину 1, після першого кроку вона дорівнює 2, після другого - 4, після тре...
