Швидке сортування це внутрішній алгоритм, який базується на стратегії «розділяй і володарюй». У цьому:

• Масив елементів неодноразово ділиться на частини, доки його не буде неможливо розділити далі.
• Він також відомий як сортування обміну розділами .
• Для розділення елементів використовується ключовий елемент (опорна точка).
• Один лівий розділ містить усі ті елементи, які менші за опорну, а інший правий розділ містить усі елементи, які більші за ключовий елемент.

Сортування злиттям є зовнішнім алгоритмом і базується на стратегії «розділяй і володарюй». У цьому:

• Елементи розбиваються на два підмасиви (n/2) знову і знову, поки не залишиться лише один елемент.
• Сортування злиттям використовує додаткову пам’ять для сортування допоміжного масиву.
• Сортування злиттям використовує три масиви, де два використовуються для зберігання кожної половини, а третій зовнішній використовується для зберігання остаточного відсортованого списку шляхом об’єднання інших двох, і кожен масив потім сортується рекурсивно.
• Нарешті, усі підмасиви об’єднуються, щоб отримати розмір елемента масиву «n».

Швидке сортування проти сортування злиттям

Поділ елементів у масиві: під час сортування злиттям масив ділиться лише на 2 половини (тобто n/2). тоді як у разі швидкого сортування масив розбивається на будь-яке співвідношення. При швидкому сортуванні немає обов’язкового розділення масиву елементів на рівні частини. Найгірша складність: найгірша складність швидкого сортування становить O(n^2), оскільки в найгіршому випадку потрібно багато порівнянь. тоді як у сортуванні злиттям найгірший і середній випадки мають однакову складність O(n log n). Використання з наборами даних: сортування злиттям може добре працювати з будь-якими типами наборів даних, незалежно від їх розміру (великого чи малого). тоді як швидке сортування не може добре працювати з великими наборами даних. Потреба в додатковому просторі для зберігання: сортування злиттям не працює, оскільки воно вимагає додаткового простору для зберігання допоміжних масивів. тоді як швидке сортування є на місці, оскільки воно не потребує додаткового зберігання. Ефективність: Сортування злиттям є більш ефективним і працює швидше, ніж швидке сортування у випадку більшого розміру масиву або наборів даних. тоді як швидке сортування є більш ефективним і працює швидше, ніж сортування злиттям у випадку меншого розміру масиву або наборів даних. Метод сортування: швидке сортування – це внутрішній метод сортування, коли дані сортуються в основній пам’яті. тоді як сортування злиттям — це зовнішній метод сортування, при якому дані, які потрібно відсортувати, не можуть бути розміщені в пам’яті та потребують допоміжної пам’яті для сортування. Стабільність: сортування злиттям є стабільним, оскільки два елементи з однаковими значеннями з’являються в тому самому порядку у відсортованому виведенні, як і у вхідному невідсортованому масиві. тоді як швидке сортування нестабільне в цьому сценарії. Але його можна зробити стабільним за допомогою деяких змін у коді. Бажано для : Швидке сортування є кращим для масивів. тоді як сортування злиттям є кращим для пов’язаних списків. Локальність посилання: Quicksort демонструє хорошу локальність кешу, і це робить швидке сортування швидшим, ніж сортування злиттям (у багатьох випадках, як у середовищі віртуальної пам’яті).