Merge Sort (Сортування злиттям), dev64

Programming

Сортування злиттям полягає в послідовному розподілі сортованого масиву навпіл, сортування половинок окремо, а потім злиття двох відсортованих масивів в один результуючий. Розподіл навпіл відбувається рекурсивно, доти, поки розмір сортованого масиву не стане 1 або 2. Якщо розмір масиву 1, то повертаємо новий масив з одного елемента (нічого сортувати не треба), якщо розмір 2, тоді порівнюємо 2 елементи і повертаємо масив із 2 елементів або в тому ж порядку, або в переставленому. Залежно від того, чи правильно йдуть елементи у вихідному масиві.

Нижче вихідний код. Функція merge() здійснює злиття двох відсортованих масивів на один (Використовується всередині mergeSoft()). Функція mergeSort() – рекурсивно сортує та мержить.

• testMerge() - показує роботу merge()
• testMergeSoft() - тестує mergeSoft()

Асимптотична складність такого алгоритму сортування O(n * ln n). Ще важливо знати, що більш повільні алгоритми можуть працювати швидше при деякому діапазоні від (0 до n>0). Тому не завжди швидший алгоритм виграє у повільнішого. Наприклад, якщо порівнювати сортування вставкою із сортуванням злиттям, то вийде, що Merge Sort виграє у простого сортування вставкою тільки за досить великих n. Першоджерело свідчить, що сортування злиттям виграє у сортування вставкою при n> 30. Мені здається, що це число може бути і більшим через необхідність виділення додаткової пам'яті.

---