У нас есть два массива <tex>A</tex> и <tex>B</tex> (фактически это будут две части одного массива, но для удобства будем писать, что у нас просто два массива). Нам надо получить массив <tex>C</tex> размером <tex>|A| + |B|</tex>. Для этого можно применить процедуру слияния. Эта процедура заключается в том, что мы сравниваем элементы массивов (начиная с начала) и меньший из них записываем в финальный. И затем, в массиве у которого оказался меньший элемент, переходим к следующему элементу и сравниваем теперь его. В конце, если один из массивов закончился, мы просто дописываем в финальный другой массив. После мы наш финальный массив записываем заместо двух исходных и получаем отсортированный участок.
Алгоритм Ниже приведён псевдокод процедуры слияния формально можно записать следующим образом:, который сливает две части массива A — [left; mid) и [mid; right)
Будет происходить слияние частей [left, middle) и [middle, right] <pre>// слияние двух частей одного массива с помощью временного// left - левая граница, right - правая, middle - серединаmerge Merge(array aA, int left, int middlemid, int right) : i it1 = left, j = middle, k 0 it2 = 0; array temp result = new arrayint[a.size()right - left]; while i left + it1 < middle mid and j mid + it2 <= right: if (aA[jleft + it1] < aA[imid + it2]): temp result[k+it1 +it2] = aA[jleft +it1] it1 +];= 1 else: temp result[k+it1 +it2] = aA[imid +it2] it2 +];= 1 while i left + it1 < middlemid: temp result[k+it1 +it2] = aA[ileft +it1] it1 +];= 1 while j mid + it2 <= right: temp result[k+it1 +it2] = aA[jmid +it2] it2 +];= 1 for (int t i = 0; t != k; tto it1 ++)it2: a A[tleft + i] = tempresult[t];// в конце a[1..ki] это будет отсортированный массив</pre>
===Рекурсивный алгоритм===
