Сортування злиттям: опис роботи алгоритму і відмінностей від інших видів впорядкування даних

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

Все різноманіття алгоритмів сортування можна розділити на дві категорії: упорядкування масивів і розташування в певному порядку файлів. Перший тип об'єктів може розташовуватися не тільки в оперативній пам'яті, але і на деякій носії за умови, що доступ до нього відкритий безпосередньо. Друга категорія об'єктів повинна знаходитися на матеріальному носії: диску або магнітній стрічці.

Ключова відмінність між упорядкуванням елементів масиву і розташуванням у заявленому порядку файлів полягає в тому, що всі члени масиву доступні в будь-який момент часу при зверненні до них, а отже, процес сортування починається відразу з моменту запуски процедури без зупинок, пов'язаних з недоступністю того чи іншого елемента. У той же час при упорядкуванні файлів в конкретний момент часу доступ може бути наданий тільки до обмеженого набору членів.

Досить часто для упорядкування файлів застосовується сортування злиттям, яка розроблена на фундаментальних принципах розташування елементів у певному порядку. У загальному випадку процедуру сортування можна описати таким чином: певний сегмент даних виділяється і використовується як ключ. Як приклад можна розглянути приклад сортування поштових відправлень за вказаною індексом. В результаті алгоритм не виробляє повний аналіз інформації, але при цьому з високою часткою ймовірності сортує необхідні елементи.

Основна відмінність послідовних файлів від файлів з наданням прямого доступу полягає в тому, що вони можуть розміщуватися на носіях, до яких складно організувати постійний прямий доступ. Крім того, такі файли зазвичай не використовують фіксовану довжину для збережених записів. Через цих особливостей послідовні файли застосовуються тільки в двох ситуаціях:

— при необхідності використання носія інформації, орієнтованого на послідовний доступ-

— коли зручно використовувати змінну довжину записів.

Сортування злиттям досить часто використовується в сучасних програмних засобах. Пов'язано це з широким розповсюдженням послідовних файлів. Наприклад, практично всі текстові файли носять послідовний характер. Незважаючи на зручність розгляду послідовно організованого файлу як масиву даних, такий підхід неможливий, т. К. До всіх елементів файлу звернутися неможливо апаратно, фізично.

Сортування злиттям стала, по суті, єдиним способом для сортування послідовних файлів. Незважаючи на те, що сьогодні існують інші методи упорядкування послідовних файлів, цей метод залишається одним з найпопулярніших. Сортування природним злиттям передбачає поділ файлу на дві частини, рівні за обсягом інформації. Далі з кожного файлу відбувається поступове зчитування кожного елемента з тих, які доступні зараз. Впорядковані елементи розташовуються в необхідному порядку в третьому файлі, який надалі розділяється на два подібних за розміром. Таким чином і виробляється сортування злиттям. Паскаль, Сі, Basic - більшість відомих мов програмування підтримують реалізацію даного типу впорядкування послідовних файлів.