Алгоритм делит исходный массив на
n
частей по количеству доступных приложению процессоров. Далее следует
параллельная область, в которой каждый поток выполняет сортировку слиянием независимо
друг от друга. В конце области обеспечивается синхронизация потоков –
выполняется ожидание завершения вычислений всех потоков; далее все потоки
завершаются – дальнейшие вычисления продолжает выполнять только основной поток.
Им и выполняется слияние n частей массива
в один упорядоченный.
void
merge (int *mas,int first,int
mid,int last)
{
int *Temp_mas = new
int[Max_size];
int first1=first;
int last1=mid;
int first2=mid+1;
int last2=last;
int index=first1;
for (;(first1<=last1) &&
(first2<=last2);++index)
{
if
(mas[first1]<mas[first2])
{
Temp_mas[index]=mas[first1];
++first1;
}
else
{
Temp_mas[index]=mas[first2];
++first2;
}
}
for
(;first1<=last1;++first1,++index)
Temp_mas[index]=mas[first1];
for
(;first2<=last2;++first2,++index)
Temp_mas[index]=mas[first2];
for
(index=first;index<=last;++index)
mas[index]=Temp_mas[index];
delete[] Temp_mas;
}
void
mergesort (int *mas,int first,int
last)
{
if (first<last)
{
int
mid=(first+last)/2;
mergesort(mas,first,mid);
mergesort(mas,mid+1,last);
merge(mas,first,mid,last);
}
}
void
parallel_mergesort(int *mas, int count)
{
int
count_stream=omp_get_num_procs();
int part= count/count_stream;
int first, last;
#pragma omp parallel private(first,last)
{
#pragma omp for
for(int i=0;
i<count_stream; i++)
{
first=i*part;
if(i==(count_stream-1))
last=count-1;
else
last=first+part-1;
mergesort(mas,first,last);
}
}
int mas_iter[100];
for(int i=0;
i<count_stream;i++)
{
first=i*part;
mas_iter[i]=first;
};
int
*tmp_mas = new int[Max_size];
bool flag= true;
int j=0;
while(flag==true)
{
int tmp_val=10000;
int tmp_iter=-2;
for(int
i=0; i<count_stream; i++)
{
if((mas_iter[i]!=-1)&&(mas[mas_iter[i]]<
tmp_val))
{
tmp_val=mas[mas_iter[i]];
tmp_iter=i;
}
}
last=-3;
if(tmp_iter==(count_stream-1))last=count-1;
else last=tmp_iter*part +part -1;
if(tmp_iter>=0)
{
tmp_mas[j]=mas[mas_iter[tmp_iter]];
j++;
}
if(mas_iter[tmp_iter]<last)
mas_iter[tmp_iter]++;
else
mas_iter[tmp_iter]=-1;
flag=false;
for(int
i=0; i<count_stream; i++)
if(mas_iter[i]!=-1) flag=true;
}
for(int i =0 ;
i<count; i++)
mas[i]=tmp_mas[i];
delete[]
tmp_mas;
}