Предыдущая часть: Как говорилось ранее, merge sort это алгоритм внешней сортировки с поcледовательным доступом. Если посмотреть на большинство исходников merge sort, размещённых на ресурсах по программированию, то можно заметить, что ничем внешним и последовательным там не пахнет. Реализуется обычный внутренний алгоритм, часто через рекурсию, и поэтому он становится очень похож на quicksort. Да Я сразу делал упор на внешнюю сортировку и последовательный доступ, эмулировав его через массив и текущую позицию в массиве...
Предыдущая часть: Алгоритм сортировки слиянием (merge sort) очень похож на quicksort, а также на другие алгоритмы семейства Divide and Conquer (Разделяй и властвуй). Суть Divide and Conquer в том, чтобы разбивать большую задачу на более мелкие, пока не получим элементарные задачи. Решив элементарные задачи, мы решаем и задачи верхнего уровня. В случае с сортировкой массив делится на 2 части, затем каждая часть делится ещё на 2, и т.д. Так мы очень быстро приходим к размеру части в 1 элемент, даже если начинали с очень большого...