Всем привет. Объясните мне пожалуйста алгоритм внешней сортировки "сбалансированное двухпутевое слияние" на пальцах. Что смог понять сам(вроде бы): Имеется массив, который необходимо отсортировать. Разбиваем его на 2 части и сортируем каждую часть по отдельности. А дальше не пойму. Инфу в инете читал, поэтому ссылки смысла нет давать) Заранее спасибо.

ап

Я бегло просмотрел описания, и я понял алгоритм так (не ручаюсь).

Был исходный массив длины N, мы каким-то образом (не важно, каким) разбили его на два массива длины N/2. Дальше мы обратно объединяем их, но уже в пары: первый элемент первого массива с первым элементом второго массива, второй элемент со вторым, и т.д. Причём в каждой паре мы записываем сначала меньшее число, потом большее.

Получилось у нас N/2 пар (каждая пара - внутри отсортирована). Теперь мы будем объединять пары в четвёрки: т.е. снова разбиваем массив пар на две половинки, затем объединяем каждую пару с соответствующей парой, сортируя их во время этого объединения. В итоге получится N/4 отсортированных четвёрок.

И т.д., размер группы будет каждый раз удваиваться, пока мы не дойдём до размера N - тогда алгоритм заканчивается.

Время работы - O (N log N) - т.к. всего проходов будет log N, поскольку размер группы удваивается каждый раз.

RiG1,  всё просто: есть два отсортированных (допустим по возрастанию) массива - до этого ты сам дошёл - а далее делаем следующую штуку:

смотрим первые элементы этих массивов и выбираем меньший - он будет первым в результирующем массиве. Если он был выбран из первого массива, то в 
том массиве, из которого выбрали минимальный переходим к следующему элементу. И  повторяем так пока не кончится один из массивов. После этого остатки оставшегося дописываем к результирующему.

Пример:

a = [1][3][5][5][13]
b = [0][3][4]

сравниваем первые элементы: минимальный в массиве b забираем его в результирующий:
с = [0]

a = [1][3][5][5][13]
b = [3][4]

сравниваем новые первые элементы: минимальный в массиве a забираем его в результирующий:
с = [0][1]

a = [3][5][5][13]
b = [3][4]

сравниваем новые первые элементы: минимальный однозначно не определяется, можно забирать из любого:
с = [0][1][3]

a = [5][5][13]
b = [3][4]

далее будут выбраны [3] и [4] из массива b  и переписан остаток из a.