Алгоритм
сортировки, который упорядочивает списки (или другие структуры данных, доступ к
элементам которых можно получать только последовательно, например — потоки) в
определённом порядке.
1.
Сортируемый массив разбивается на две части примерно одинакового
размера;
2.
Каждая из получившихся частей сортируется отдельно, например — тем
же самым алгоритмом;
3.
Два упорядоченных массива половинного размера соединяются в один.
Рекурсивное
разбиение задачи на меньшие происходит до тех пор, пока размер массива не
достигнет единицы (любой массив длины 1 можно считать упорядоченным).
Псевдокод
алгоритма слияния без "прицепления" остатка на C++-подобном языке:
L = *In1;
R = *In2;
if( L == R )
{
*Out++ = L;
In1++;
*Out++ = R;
In2++;
}
else if( L < R )
{
*Out++ = L;
In1++;
}
else
{
*Out++ = R;
In2++;
}
Анализ
сложности – Королев-Миков страницы 122!!!
