Сортировка слиянием
Материал из Algocode wiki
Содержание
Сортировка слиянием (MergeSort)
Описание алгоритма
Допустим, нам надо отсортировать массив из $N$ чисел. Заметим, что если в нем только одно число($N = 1$), то массив уже отсортирован. Иначе предположим, что массивы размеров меньше $N$ мы уже умеем сортировать. Тогда сделаем следующее: разделим массив на две примерно равные части (просто делим пополам), отдельно отсортируем левую, отдельно отсортируем правую часть. Нам останется только объединить эти два массива и получить результат.
Пример:
Пусть дан массив $a = [7, 0, 1, 3, 5, 2, 6, 4]$.
0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
---|---|---|---|---|---|---|---|
7 0 1 3 5 2 6 4 | |||||||
7 0 1 3 | 5 2 6 4 | ||||||
7 0 | 1 3 | 5 2 | 6 4 | ||||
7 | 0 | 1 | 3 | 5 | 2 | 6 | 4 |
Функция Merge
Научимся сливать (объединять) два отсортированных массива.