Листинг 1 Абстрактное обменное слияние

template <typename T>

void MergeSort(T * RES, int left, int m, int right) {

int i,j;

T * WORK = new T[right];

for(i=m+1;i>left;i--) WORK[i-1]=RES[i-1];

for(j=m;j<right;j++) WORK[right+m-j]=RES[j+1];

for(int k=left;k<=right;k++)

if(WORK[j]<WORK[i])

RES[k]=WORK[j--];

else

RES[k]=WORK[i++];

}

Данная программа выполняет слияние двух файлов без использования служебных меток, путем копирования второго массива в массив WORK в обратном порядке, когда сразу за концом первого массива следует конец второго (т.е., устанавливая на WORK битонный порядок). Первый цикл for перемещает первый массив, после чего i указывает на left, что означает готовность начинать слияние. Второй цикл for перемещает второй массив, после чего j указывает на right. Затем в процессе слияния (третий цикл for) наибольший элемент служит служебной меткой независимо от того, в каком файле он находится. Внутренний цикл этой программы достаточно короткий (сравнение, перенос в RES, увеличение значений i или j на единицу, увеличение на единицу и проверка значения k).

Дата добавления: 2015-08-17