Сортировка слиянием. Написать функцию join(int low, int middle, int high, int array[high]), которая считает, что в массиве array есть два последовательно идущих упорядоченных фрагмента: array[low] … array[middle-1] и array[middle] … array[high-1]. Функция создаёт временный массив на high-low элементов, формирует там упорядоченную последовательность и записывает её обратно в array[low] … array[high-1].
- Алгоритм слияния: циклически выбирать меньшее между array[low] и array[middle] и добавлять его во временный массив, увеличивая low или middle соответственно. Когда один фрагмент закончится, числа во втором будут точно больше остальных, они дописываются в конец.
Написать функцию joinsort(int n, int array[n]), которая сортирует массив array методом простого слияния.
- Алгоритм простого слияния (да, не рекурсивный, и что?):
- попарно слить соседние элементы в упорядоченные пары
- попарно слить соседние пары в упорядоченные четвёрки
- …
попарно слить соседние 2k-1-ки в упорядоченные 2k-ки
- …
- PROFIT!
Потренируйтесь на массивах размера 2n, но затем адаптируйте алгоритм для массивов любого размера (high иногда будет меньше, чем middle+2k-1, вот и всё).
- Напишите программу, которая вводит N ⩽ 300000, затем массив из N целых, а затем выводит его в отсортированном виде.
15 3 1 4 1 5 3 1 4 1 5 3 1 4 1 5
1 1 1 1 1 1 3 3 3 4 4 4 5 5 5