Dima T...
Например есть последовательности [4][2][55][48][2][12] число в скобках это количество элементов в каждой последовательности. В каком порядке их мержить?
...

Есть такой алгоритм - "естественная двусторонняя сортировка слиянием" (nature merge sort
или nature 2-way merge sort)
(у которой есть "неестественные" вариации - вроде двоичной двусторонней бла-бла-бла, и далее - многоветочные истории, которые, правда, вроде как скисают на большом числе веток и больших сортируемых объемах - я в них не разбирался детально.)
не поленись, погугли.

Идею алгоритма приписывают Кнуту.
Смысл в том, чтобы сливать с двух краев в середину (свеча слияния горит с двух концов).
То есть на первом шаге алгоритма слияние идет в таком порядке:

[4][2][55][48][2][12] || x||x xx||xx
при этом на фазе самого слияния используют двоичный поиск.

То есть
Сортированный_результат = ГоримСДвухСторон(Разбиение_на_Сортированные_диапазоны(Сортируемый_Список))

В принципе, алгоритму не требует наличия сколь-нибудь протяженных предварительно сортированных поддиапазонов.
Но, если сортируемый список представляет чистый белый шум,
то у некоторых имплементаторов есть мнение, что разумно натравить на БелыйШум
сортировку вставкой, с размером итоговых сортированных поддиапазонов на 8 - 16 элементов, что и создаст стартовую точку для горения с двух сторон.

Еще есть изобретения in-place слияния.
имхо, годное к разглядыванию обсуждение:
http://stackoverflow.com/questions/2571049/how-to-sort-in-place-using-the-merge-sort-algorithm

booby,

существенная деталь - в свечном производстве
с головы ищут неубывающую подпоследовательность, а с хвоста - невозрастающую.
т.е. в исходной идее, в голове - [4][2][55] - это возрастающие поддиапазоны (asc),
а [48][2][12] - убывающие (desc) поддиапазоны

Dima T,
код внимательно разглядывать не могу, но,
кажется, ты не обратил внимание на то, что свечка при слиянии подмассивов
заведомо рассчитывает на то, что имеет дело с уже отсортированными диапазонами.
Поэтому не боится использовать двоичный поиск на фазе слияния.

Пусть сливаются отрезки с длинами а)[4](левый) и б)[12] (правый)


/*текущая позиция в а */ и = старт_а
голова_цикла:
номер_позиции_а(и)_в_б = двоичным поиском ищем позицию(б)
от текущего начала не перелитой части б до найденной и вываливаем все б(ж) в область слияния
вываливаем в область слияния элементы а, пока они не больше а(и)
устанавливаемся в новую позицию и в а
Если диапазоны не кончились, то ГОУ ТУ голова_цикла

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

SashaMercuryА что будет с вашим алгоритмом, если массивы будут стыковаться как две расчески?


(Кнута это алгоритм, Дональда Эрвина,
который русский выучил только за то, что им разговаривал Андрей Петрович Ершов.
Чтобы книжки его читать в оригинале.
)

Вопрос правильный.
Остановится при перехлесте.
Так как слежение за перехлестом встроено в (реальный) алгоритм.

Без опасности перехлеста работает 2-way.
Который не смотрит на то, есть ли естественным образом сортированные куски, а вменяет сливаемым диапазонам быть сортированными путем слияния диапазонов, начиная 1.

А так как первые пять шагов слияния в 2way, стартующего с единичных крайних элементов занимаются слиянием слишком коротких массивов, сам Кнут настаивает - не надо так делать.
Надо натравить сортировку вставками для разбиения массива на сортированные диапазоны
размером в 16 в качестве первого шага, а потом можно включать 2way

Dima TМожет я неправильно понял описание твоего алгоритм

Сейчас покопался еще раз в началах и концах.
Нашел следующее - в варианте, описанном у Кнута (5.2.4), действительно, слева ищутся
возрастающие, справа убывающие диапазоны.
При этом само слияние совмещено с просмотром.
Такая версия подачи затрудняет общее понимание идеи.

Стартуя с приведенной мной ссылки можно добраться до книжки "Элементарные алгоритмы",
в которой изложена упрощенная версия, не ждущая убывающего диапазона с правой стороны.

Имхо этот вариант проще для понимания и после него легче будет смотреть в книжку Кнута.

Пусть дан для сортировки массив
M[8, 12, 14 , 0, 1, 4, 11, 2, 3, 5, 9, 13, 10, 6, 15, 7]

И известно, что элементов в нем 16

N=16;
merge_step = 0

0) Выделим память размером в полученный массив (N)
M[8, 12, 14 , 0, 1, 4, 11, 2, 3, 5, 9, 13, 10, 6, 15, 7]
-- доп. память N=16
P[x, xx, xx , x, x, x, xx, x, x, x, x, xx, xx, xx, xx, x]

<<ДЕЛАЙ ВСЕГДА>>
ileft_start = 1; //начало левого диапазона
ileft_stop = 1; //конец левого диапазона
iright_start = N; // начало правого диапазона
iright_stop = N; // конец правого диапазона

merge_leftpos_start = 1; // позиция, начиная с которой будем дописывать в массив промежуточного результата
// мы считаем с 1, хоть форум и по C++

merge_rightpos_start = N; // 16 - позиция, в которую будем дописывать справа

//шаг слияния, первый рабочий шаг будет 1 (нечетный шаг)
(на нечетных шагах будем дописывать в левую часть выделенной памяти, на четной - в правую
)
merge_step = 1;
<<ЦИКЛ ПОКА ПРОБЕГА ПОКА НЕ ПРОСМОТРИМ M ЦЕЛИКОМ (ileft_stop < iright_start)>>

//ищем позицию в которой завершается первый неубывающий диапазон слева
ileft_stop = поиск_слева(ileft_start ); // здесь получим 3 на первом шаге для конкретного массива

ЕСЛИ ileft_stop >= N то алгоритм завершен, т.к. массив полностью сортирован.

// вот что мы нашли
M[ 8, 12, 14 | , 0, 1, 4, 11, 2, 3, 5, 9, 13, 10, 6, 15, 7]
//
//ищем позицию упорядоченного убывающего диапазона справа
iright_start = поиск_справа(iright_stop)// получим 15 на первом просмотре

ЕСЛИ ileft_stop >=iright_start то случился перехлест, любим левый край: iright_start = ileft_stop + 1
//
//вот что мы нашли
M[ 8, 12, 14 |, 0, 1, 4, 11, 2, 3, 5, 9, 13, 10, 6,| 15, 7 ]
// здесь мы уже знаем какой размер займет результат
// - 5 элементов = (ileft_stop - ileft_start +1) + (iright_stop - iright_start+1)
// но, т.к. у нас две позиции вставки - левая и правая, то пусть их формирует процедура
//слияния, которой мы будет рассказывать, в какую сторону - левую или правую ей надо доливать, а она нам за это вернет новую позицию после долива

Если Нечетно(merge_step)
Сливаем_в_M(ileft_start, ileft_stop, iright_start, iright_stop,merge_leftpos_start,Слева_Если_Нечетно(merge_step));
Иначе
Сливаем_в_M(ileft_start, ileft_stop, iright_start, iright_stop,merge_rightpos_start, Слева_Если_Нечетно(merge_step));

// результат
M[ 8, 12, 14 | , 0, 1, 4, 11, 2, 3, 5, 9, 13, 10, 6, 15, 7]
P[7, 8, 12, 14, 15, x, xx, x, x, x, x, xx, xx, xx, xx, x]

merge_step = NOT merge_step
ileft_start = ileft_stop + 1; // 4 после первого прохода
iright_stop = iright_start - 1; //14 после первого прохода
<<КОНЕЦ ЦИКЛА ПОКА>>
// завершен один полный пробег по M
// меняем местами M и P - swap
ОБМЕНЯТЬ(M,P);
<<КОНЕЦ ДЕЛАЙ ВСЕГДА>>
---------- ------------------------------------
//т.к. у нас не программа а лог ее выполнения - пишем дальше.
//сейчас мы на втором проходе внутри цикла <<ЦИКЛ ПОКА ПРОБЕГА ПОКА НЕ ПРОСМОТРИМ M ЦЕЛИКОМ (ileft_stop < iright_start)>>
// продолжаем...
//ищем позицию в которой завершается первый неубывающий диапазон слева
// начало у нас сейчас в 4
ileft_stop = поиск_слева(ileft_start ); // здесь получим 7 на втором шаге для конкретного массива
// вот что мы нашли
M[8, 12, 14, 0, 1, 4, 11 |, 2, 3, 5, 9, 13, 10, 6, 15, 7]

//ищем позицию упорядоченного убывающего диапазона справа
//стоп у нас в 14
iright_start = поиск_справа(iright_stop)// получим 12 на втором просмотре
// вот что мы нашли
M[8, 12, 14, 0, 1, 4, 11 |, 2, 3, 5, 9,| 13, 10, 6 |, 15, 7]
// шаг четиный, потому сливаем вправо
//!! В правый угол пишем в обратной последовательности
Если нечетно
Сливаем_в_M(ileft_start, ileft_stop, iright_start, iright_stop,merge_leftpos_start, Слева_Если_Нечетно(merge_step));
Иначе
Сливаем_в_M(ileft_start, ileft_stop, iright_start, iright_stop,merge_rightpos_start, Слева_Если_Нечетно(merge_step));
// резултьтат
M[8, 12, 14, 0, 1, 4, 11 |, 2, 3, 5, 9,| 13, 10, 6 |, 15, 7]
P[7, 8, 12, 14, 15, x, xx, x, x, 13, 11, 10, 6, 4, 1, 0]

и так далее...
-------------------------------------
натуральной такую свечку Кнут называет из-за того, что она двигается в поисках однородной последовательности столько, сколько может.

Мне кажется, на том же основании ее можно было бы назвать жадной свечкой.
Она то жадная, но всегда не знает, сколько сейчас ей хотеть, потому собирает всякий раз по копеечке.

Кнут оценивает ее как в среднем уступающую быстрой сортировке, но выигрывающей на почти сортированном массиве.
А на таком специальном почти сортированном, который за одно слияние становится сортированным, ее трудно обогнать.
В записи Кнута просмотры осуществляются с обоих концов разом и совмещены с копированием в результат (слиянием).
Главный недостаток - в этой версии алгоритму всегда неизвестно, где расположены сейчас границы диапазонов.
Хотя по мере заполнения P все размеры получающихся диапазонов известны, и после первого swap их можно было бы поддерживать.
Но, такую версию, вроде как, выписывать не принято.

Считается, что если входной массив сортированный, но не настолько, чтобы обойтись одним-двумя проходами
главного цикла, то дешевле и умнее сразу вооружиться 2way версией
(подкрученной до стартовой insertion sort), которая путем применения вмененной арифметики
всегда знает границы своих сортированных частей для четного случая.

А нечетный сводится к четному путем определения места для нечетного элемента
двоичным поиском на последнем шаге сортировки.

не ждущая убывающего диапазона с правой стороны.
это дефект - считать не написанным