Розділяй і володарюй
Отже, ми навчилися об’єднувати відсортовані колекції значень. Можна сказати, що друга частина алгоритму сортування злиттям – безпосередньо злиття – вже розібрана.
Однак необхідно ще зрозуміти, як від вихідного несортованого масиву чисел дістатися до декількох відсортованих, які можна буде злити.
Розглянемо першу стадію алгоритму і навчимося розділяти масиви.
В цьому немає нічого складного – вихідний список значень ділиться навпіл, потім кожну частину також роздвоюється, і так до тих пір, поки не вийдуть зовсім маленькі блоки.
Довжина таких мінімальних елементів може бути дорівнює одиниці, тобто вони можуть самі по собі бути відсортованим масивом, проте це не обов’язкова умова. Розмір блоку визначається заздалегідь, а для його упорядкування може використовуватися будь-який відповідний алгоритм сортування, ефективно працює з масивами малих розмірів (наприклад, швидке сортування або сортування вставками).
Виглядає це наступним чином.
// вихідний масив
{34, 95, 10, 2, 102, 70};
// перший поділ
{34, 95, 10} і {2, 102, 70};
// друге поділ
{34} і {95, 10} і {2} і {102, 70}
Отримані блоки, що складаються з 1-2 елементів, дуже просто впорядкувати.
Після цього необхідно об’єднати вже відсортовані маленькі масиви попарно, зберігши порядок членів, що ми вже навчилися робити.
