Участник:Bkmish/Сортировка слиянием (последовательный и параллельный варианты)

Свойства и структура алгоритмов

Общее описание алгоритма

Алгоритм сортировки слиянием (англ. merge sort) является методом упорядочивания списков или других структур данных, в которых доступ к элементам может быть получен только последовательно. Этот алгоритм был разработан Джоном фон Нейманом в 1945 году и является хорошим примером использования принципа «разделяй и властвуй», поскольку основан на разбиении главной задачи на более мелкие подзадачи, которые решаются, например, с помощью рекурсивного вызова или непосредственно, если количество элементов рассматриваемой структуры достаточно мало. После этого полученные результаты комбинируются для получения решения основной задачи.

Математическое описание алгоритма

В общем виде алгоритм сортировки слиянием выглядит следующим образом:

1. Разделение: исходный массив разделяется на две равные или приближенно равные части. Если массив состоит из одного элемента, он считается отсортированным. Если массив содержит более одного элемента, процесс разделения продолжается рекурсивно, пока в подмассивах не останется по одному элементу, такие подмассивы по определению считаются отсортированными.
2. Сортировка и слияние: отсортированные подмассивы сливаются в один. Процесс слияния осуществляется путем сравнения первых элементов каждого подмассива. Меньший элемент перемещается в результирующий массив, и индекс в соответствующем подмассиве увеличивается на единицу. Этот процесс продолжается, пока не будут исчерпаны все элементы в обоих подмассивах

Вычислительное ядро алгоритма

Вычислительное ядро алгоритма сортировки слиянием − это процесс (состоящий из сравнений элементов и перемещения оставшихся элементов) слияния двух отсортированных подмассивов в один отсортированный массив. Этот процесс занимает большую часть времени работы алгоритма.

Макроструктура алгоритма

Макроструктура предложенного алгоритма сортировки слиянием состоит из двух макроопераций, соответствующих этапам алгоритма:

1. mergesort: это рекурсивная функция, которая реализует алгоритм сортировки слиянием. Она делит массив на две половины, параллельно сортирует их, а затем сливает в один отсортированный массив;
2. merge: эта функция сливает два отсортированных подмассива, полученных в результате предыдущей макрооперации, в один отсортированный массив.

Схема реализации последовательного алгоритма

void mergesort(int a[],int i,int j)
{
   int mid;
       
   if(i<j)
   {
       mid=(i+j)/2;
       
       #pragma omp parallel sections 
       {

           #pragma omp section
           {
               mergesort(a,i,mid);   //left recursion
           }

           #pragma omp section
           {
               mergesort(a,mid+1,j);   //right recursion
           }
       }

       merge(a,i,mid,mid+1,j);   //merging of two sorted sub-arrays
   }
}
 
void merge(int a[],int i1,int j1,int i2,int j2)
{
   int temp[1000000];   //array used for merging
   int i,j,k;
   i=i1;   //beginning of the first list
   j=i2;   //beginning of the second list
   k=0;
   
   while(i<=j1 && j<=j2)   //while elements in both lists
   {
       if(a[i]<a[j])
           temp[k++]=a[i++];
       else
           temp[k++]=a[j++];
   }
   
   while(i<=j1)   //copy remaining elements of the first list
       temp[k++]=a[i++];
       
   while(j<=j2)   //copy remaining elements of the second list
       temp[k++]=a[j++];
       
   //Transfer elements from temp[] back to a[]
   for(i=i1,j=0;i<=j2;i++,j++)
       a[i]=temp[j];
}

Последовательная сложность алгоритма

Последовательная версия алгоритма сортировки слиянием имеет временную сложность [math]\displaystyle{ \Theta(n \log n) }[/math] в лучшем, среднем и худшем случаях. Это происходит потому, что алгоритм разделяет массив на две половины на каждом уровне рекурсии (что требует [math]\displaystyle{ \log n }[/math] уровней), а затем сливает [math]\displaystyle{ n }[/math] элементов на каждом уровне, что дает общую временную сложность [math]\displaystyle{ \Theta(n \log n) }[/math]

Ресурс параллелизма алгоритма

Ресурсом параллелизма в данном алгоритме является возможность независимого выполнения рекурсивных вызовов функции mergesort() для левой и правой половин массива. Эти вызовы обрабатывают разные части данных и не зависят друг от друга, что позволяет выполнять их одновременно на разных потоках.

Параллельная версия алгоритма сортировки слиянием может быть выполнена с использованием различных подходов и, следовательно, имеет различные временные сложности. Так, используя один из алгоритмов распараллеливания, приведенный ниже в пункте 2.3, можно достичь сложности [math]\displaystyle{ \Theta(\log^2 n) }[/math]

В параллельной сортировке слиянием с использованием мы распараллеливаем рекурсивные вызовы сортировки для левой и правой половин массива. Это означает, что в идеальном случае (когда количество потоков неограниченно и затраты на создание потоков и синхронизацию между ними игнорируются) оба этих вызова могут выполняться одновременно. Таким образом, максимальное время, необходимое для сортировки половин массива, будет [math]\displaystyle{ \log n }[/math] (а не [math]\displaystyle{ 2\log n }[/math], как было бы при последовательной сортировке), что дает нам временную сложность [math]\displaystyle{ \Theta(\log n) }[/math] для сортировки каждой половины массива.

После того как обе половины массива отсортированы, нам еще нужно их объединить. Этот шаг выполняется последовательно и имеет временную сложность [math]\displaystyle{ \Theta(n) }[/math]. Если мы считаем, что время слияния доминирует над временем сортировки половин массива (что может быть верно для больших массивов), то общая временная сложность алгоритма будет [math]\displaystyle{ \Theta(n \log n) }[/math], как и для последовательной сортировки слиянием.

Однако, если мы считаем, что время слияния не доминирует (что может быть верно для маленьких массивов), то общая временная сложность алгоритма будет [math]\displaystyle{ \Theta(\log^2 n) }[/math]. Это получается из-за того, что мы делаем [math]\displaystyle{ \log n }[/math] рекурсивных вызовов, и в каждом вызове мы выполняем операцию, которая требует [math]\displaystyle{ \log n }[/math] времени (то есть, сортировку половины массива)

Литература

• Левитин А. В. Глава 4. Метод декомпозиции: Сортировка слиянием // Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — С. 169—172. — 576 с. — ISBN 978-5-8459-0987-9
• Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — 1296 с. — ISBN 5-8459-0857-4.
• Victor J. Duvanenko "Parallel Merge Sort" Dr. Dobb's Journal & blog
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4. (p. 797-805)