Сортировка слиянием
Сортировка слиянием предполагает последовательный доступ к элементам сортируемых последовательностей. Это объясняется тем, что она была разработана для сортировки данных на устройствах последовательного доступа (магнитных лентах). Хотя никто не запрещает производить то же самое в массивах или списках. Если имеется n упорядоченных последовательностей, то получить из них общую упорядоченную последовательность достаточно просто, использую только последовательное извлечение элементов из них. При извлечении первого элемента из последовательности и переносе его в выходную следующий за ним становится первым и т.д.. Такой принцип доступа к данным имеет место при чтении последовательных файлов, поэтому слияние часто используется при сортировке файлов данных.
ОДНОКРАТНОЕ СЛИЯНИЕ. Очевидно, что если из упорядоченных последовательностей брать по одному очередному элементу из каждой, затем выбирать из них минимальный и переносить его, то выходная последовательность будет упорядоченной. Отсюда возможен самый простой способ однократного слияния : массив разбивается на n частей, каждая из них сортируется независимо, а затем отсортированные части объединяются слиянием. Текст ищите в " Вопросах без ответов " .
ЦИКЛИЧЕСКОЕ СЛИЯНИЕ. Первоначально массив разделяется на n последовательностей. Затем в каждой из них выбирается по одному элементу (первому) в таком порядке, чтобы получилась упорядоченная группа из n элементов, которая запоминается в выходной последовательности (слияние). Выходная последовательность будет состоять из групп по n элементов, каждая из которых упорядочена. Далее файл опять распределяется, но уже группами по n элементов по тем же самым n входным последовательностям. В результате слияния образуются упорядоченные группы из n*n элементов. Затем процесс повторяется группами по n*n*n и т.д.. В качестве примера рассмотрим случай с n=2 (двухпутевое слияние). Для простоты будем считать размерность сортируемого массива кратной 2.
void sort(int in[],int n, int v1[], int v2[])
{
int step,m,k0;
for (m=n; m!=1; m/=2) // Проверка на степень 2
if (m%2 !=0) return;
for (step=1 step <n; step *=2) // Слияние группами по
{ // step = 1,2,4...n/2
for (k0=0; k0 < n/2; k0 += step)
// Распределить in[], начиная с 2*k0, группy по step
// элементов в v1 и в v2, начиная с k0
for (k0=0; k0 < n; k0 += step*2)
// "Слить" по step элементов из v1 и v2, начиная с k0,
// в in[], начиная с 2*k0
}
}
Часть алгоритма, которая распределяет, начиная с 2*k0 из массива in группу из step элементов в массив v1 и такую же группу в v2, в комментариях не нуждается:
int i;
for (i=0, i<step; i++) v1[k0 + i] = in[2*k0 + i];
for (i=0, i<step; i++) v2[k0 + i] = in[2*k0 + step + i];
Часть алгоритма, выполняющего слияние, не так очевидна. В ней используются относительные индексы i1 и i2, которые последовательно " отсчитывают " элементы в группах из v1 и v2. Процесс продолжается, пока обе группы не будут "слиты". Первоначально проверяется факт окончания каждой из групп, тогда элемент берется из противоположной. В противном случае выбирается меньший элемент из двух текущих в группах:
int i1,i2;
for (i1=i2=0; i1+i2 < 2*step; )
{
if (i1==step)
{ in[2*k0+i1+i2] = v2[k0+i2]; i2++; }
else
if (i2==step)
{ in[2*k0+i1+i2] = v1[k0+i1]; i1++; }
else
if (v1[k0+i1] < v2[k0+i2])
{ in[2*k0+i1+i2] = v1[k0+i1]; i1++; }
else
{ in[2*k0+i1+i2] = v2[k0+i2]; i2++; }
}
Некоторая сложность алгоритма простого слияния состоит в слежении за группами, в результате чего получаются такие " дикие " индексы массивов. ПОРАЗРЯДНАЯ РАСПРЕДЕЛЯЮЩАЯ СОРТИРОВКА работает с двумя последовательностями целиком, не выделяя в нем групп. Слияние осуществляется как обычно, путем выбора минимального из двух текущих элементов последовательностей. Зато распределение происходит на первом шаге по значению старшего значащего бита (0/1), и по значению каждого следующего бита на очередном шаге. Алгоритм при этом упрощается настолько, что приведен в "Вопросах без ответов...".Распределение можно вести одновременно для нескольких соседних битов, при этом количество выходных массивов будет равно соответствующей степени 2.
