C++
/**
* @brief Сортировка элементов от l до r массива buf
* @param[in/out] buf - сортируемый массив
* @param[in] l - левая граница. При первой итерации l = 0
* @param[in] r - правая граница. При первой итерации r = buf.size() - 1
*
* В результате сортируются все элементы массива buf от l до r включительно.
*/
template<typename Type>
void MergeSort(vector<Type>& buf, size_t l, size_t r)
{
//! Условие выхода из рекурсии
if(l >= r) return;
size_t m = (l + r) / 2;
//! Рекурсивная сортировка полученных массивов
MergeSort(buf, l, m);
MergeSort(buf, m+1, r);
merge(buf, l, r, m);
}
/**
* @brief Слияние элементов.
* @param[in/out] buf - массив
* @param[in] l - левая граница. При певой итерации l = 0
* @param[in] r - правая граница. При первой итерации r = buf.size() - 1
* @param[in] m - граница подмассивов.
*
* Массив buf содержит два отсортированных подмассива:
* - [l; m] - первый отсортированный подмассив.
* - [m+1; r] - второй отсортированный подмассив.
* В результате получаем отсортированный массив, полученный из двух подмассивов,
* который сохраняется в buf[l; r].
*/
template<typename Type>
static void merge(vector<Type>& buf, size_t l, size_t r, size_t m)
{
if(l >= r || m < l || m > r) return;
if(r == l + 1 && buf[l] > buf[r])
{
swap(buf[l], buf[r]);
return;
}
vector<Type> tmp(&buf[l], &buf[r+1]);
for(size_t i = l, j = 0, k = m - l + 1; i <= r; i++)
{
if(j > m - l) buf[i] = tmp[k++];
else if(k > r - l) buf[i] = tmp[j++];
else buf[i] = (tmp[j] < tmp[k]) ? tmp[j++] : tmp[k++];
}
}
Существует также итеративный алгоритм сортировки, избавленный от рекурсивных вызовов. Такой алгоритм называют «Восходящей сортировкой слиянием».
// Слияние двух упорядоченных массивов
// m1 - Первый массив
// m2 - Второй массив
// l1 - Длина первого массива
// l2 - Длина второго массива
// Возвращает объединённый массив
template <class T>
T* merge(T *m1, T* m2, int l1, int l2)
{
T* ret = new T[l1+l2];
int n = 0;
// Сливаем массивы, пока один не закончится
while (l1 && l2)
{
if (*m1 < *m2)
{
ret[n] = *m1;
m1++;
l1--;
}
else
{
ret[n] = *m2;
m2++;
l2--;
}
n++;
}
// Если закончился первый массив
if (l1 == 0)
{
for (int i=0; i<l2; i++)
{
ret[n++] = *m2++;
}
}
// Если закончился второй массив
else
{
for (int i=0; i<l1; i++)
{
ret[n++] = *m1++;
}
}
return ret;
}
// Функция восходящего слияния
template <class T>
void mergeSort(T * mas, int len)
{
int n = 1, l, ost;
T * mas1;
while (n < len)
{
l = 0;
while (l < len)
{
if (l+n >= len) break;
ost = (l+n*2>len) ? (len-(l+n)) : n;
mas1 = merge(mas + l, mas + l + n, n, ost);
for (int i = 0; i<n+ost; i++) mas[l+i] = mas1[i];
delete [] mas1;
l += n*2;
}
n *= 2;
}
}
Пример: char a[] = "ASORTINGEXAMPLE"; mergeSort(a, 16); Альтернативная версия алгоритма Сортировки Слиянием.
template <typename Item>
void Merge(Item Mas[], int left, int right, int medium)
{
int j = left;
int k = medium + 1;
int count = right - left + 1;
if (count <= 1) return;
Item *TmpMas = new Item[count];
for (int i = 0; i < count; i++)
{
if (j <= medium && k <= right)
{
if (Mas[j] < Mas[k])
TmpMas[i] = Mas[j++];
else
TmpMas[i] = Mas[k++];
}
else
{
if (j <= medium)
TmpMas[i] = Mas[j++];
else
TmpMas[i] = Mas[k++];
}
}
j = 0;
for (int i = left; i <= right; i++)
{
Mas[i] = TmpMas[j++];
}
delete[] TmpMas;
}
template <typename Item>
void MergeSort(Item a[], int l, int r)
{
int m;
// Условие выхода из рекурсии
if(l >= r) return;
m = (l + r) / 2;
// Рекурсивная сортировка полученных массивов
MergeSort(a, l, m);
MergeSort(a, m + 1, r);
Merge(a, l, r, m);
}
C#
static Int32[] Merge_Sort(Int32[] massive)
{
if (massive.Length == 1)
return massive;
Int32 mid_point = massive.Length / 2;
return Merge(Merge_Sort(massive.Take(mid_point).ToArray()), Merge_Sort(massive.Skip(mid_point).ToArray()));
}
static Int32[] Merge(Int32[] mass1, Int32[] mass2)
{
Int32 a = 0, b = 0;
Int32[] merged = new int[mass1.Length + mass2.Length];
for (Int32 i = 0; i < mass1.Length + mass2.Length; i++)
{
if (b < mass2.Length && a < mass1.Length)
if (mass1[a] > mass2[b] && b < mass2.Length)
merged[i] = mass2[b++];
else //if int go for
merged[i] = mass1[a++];
else
if (b < mass2.Length)
merged[i] = mass2[b++];
else
merged[i] = mass1[a++];
}
return merged;
}
static void Main(string[] args)
{
Int32[] arr = new Int32[100];
//заполняем массив случайными числами
Random rd = new Random();
for(Int32 i = 0; i < arr.Length; ++i) {
arr[i] = rd.Next(1, 101);
}
System.Console.WriteLine("The array before sorting:");
foreach (Int32 x in arr)
{
System.Console.Write(x + " ");
}
//сортировка
arr = Merge_Sort(arr);
System.Console.WriteLine("\n\nThe array after sorting:");
foreach (Int32 x in arr)
{
System.Console.Write(x + " ");
}
System.Console.WriteLine("\n\nPress the <Enter> key");
System.Console.ReadLine();
}
Perl
@out=(5,2,8,9,4,2,7,9,4,1,6,9,0);
sub sortM{
my($array,$first,$last)=@_;
if($last>$first){
my$middle=int(($last+$first)/2);
sortM($array,$first,$middle);
sortM($array,$middle+1,$last);
my$j=0;
$work[$j++]=$$array[$_]for($first..$last);
$middle=int(($first+$last)/2)if($middle>$last);
my$n=$middle-$first+1;
for($i=$first,$j=0,$k=$n;$i<=$last;$i++){
if(($j<$n)&&(($k==(($last-$first)+1))||($work[$j]lt$work[$k]))){
$$array[$i]=$work[$j++]
}else{
$$array[$i]=$work[$k++];
}
}
}
}
sortM(\@out,0,$#out+1);
Паскаль (сортировка текстовых файлов)
Сортировка простым слиянием
Procedure MergeSort(name: string; var f: text);
Var a1,a2,s,i,j,kol,tmp: integer;
f1,f2: text;
b: boolean;
Begin
kol:=0;
Assign(f,name);
Reset(f);
While not EOF(f) do
begin
read(f,a1);
inc(kol);
End;
Close(f);
Assign(f1,'{имя 1-го вспомогательного файла}');
Assign(f2,'{имя 2-го вспомогательного файла}');
s:=1;
While (s<kol) do
begin
Reset(f); Rewrite(f1); Rewrite(f2);
For i:=1 to kol div 2 do
begin
Read(f,a1);
Write(f1,a1,' ');
End;
If (kol div 2) mod s<>0 then
begin
tmp:=kol div 2;
While tmp mod s<>0 do
begin
Read(f,a1);
Write(f1,a1,' ');
inc(tmp);
End;
End;
While not EOF(f) do
begin
Read(f,a2);
Write(f2,a2,' ');
End;
Close(f); Close(f1); Close(f2);
Rewrite(f); Reset(f1); Reset(f2);
Read(f1,a1);
Read(f2,a2);
While (not EOF(f1)) and (not EOF(f2)) do
begin
i:=0; j:=0;
b:=true;
While (b) and (not EOF(f1)) and (not EOF(f2)) do
begin
If (a1<a2) then
begin
Write(f,a1,' ');
Read(f1,a1);
inc(i);
End
else
begin
Write(f,a2,' ');
Read(f2,a2);
inc(j);
End;
If (i=s) or (j=s) then b:=false;
End;
If not b then
begin
While (i<s) and (not EOF(f1)) do
begin
Write(f,a1,' ');
Read(f1,a1);
inc(i);
End;
While (j<s) and (not EOF(f2)) do
begin
Write(f,a2,' ');
Read(f2,a2);
inc(j);
End;
End;
End;
While not EOF(f1) do
begin
tmp:=a1;
Read(f1,a1);
If not EOF(f1) then
Write(f,tmp,' ')
else
Write(f,tmp);
End;
While not EOF(f2) do
begin
tmp:=a2;
Read(f2,a2);
If not EOF(f2) then
Write(f,tmp,' ')
else
Write(f,tmp);
End;
Close(f); Close(f1); Close(f2);
s:=s*2;
End;
Erase(f1);
Erase(f2);
End;
Сортировка естественным слиянием
Procedure MergeSort(name: string; var f: text);
Var s1,s2,a1,a2,where,tmp: integer;
f1,f2: text;
Begin
s1:=5; s2:=5; {Можно задать любые числа, которые запустят цикл while}
Assign(f,name);
Assign(f1,'{имя 1-го вспомогательного файла}');
Assign(f2,'{имя 2-го вспомогательного файла}');
While (s1>1) and (s2>=1) do
begin
where:=1;
s1:=0; s2:=0;
Reset(f); Rewrite(f1); Rewrite(f2);
Read(f,a1);
Write(f1,a1,' ');
While not EOF(f) do
begin
read(f,a2);
If (a2<a1) then
begin
Case where of
1: begin
where:=2;
inc(s1);
End;
2: begin
where:=1;
inc(s2);
End;
End;
End;
Case where of
1: write(f1,a2,' ');
2: write(f2,a2,' ');
End;
a1:=a2;
End;
If where=2 then
inc(s2)
else
inc(s1);
Close(f); Close(f1); Close(f2);
Rewrite(f); Reset(f1); Reset(f2);
Read(f1,a1);
Read(f2,a2);
While (not EOF(f1)) and (not EOF(f2)) do
begin
If (a1<=a2) then
begin
Write(f,a1,' ');
Read(f1,a1);
End
else
begin
Write(f,a2,' ');
Read(f2,a2);
End;
End;
While not EOF(f1) do
begin
tmp:=a1;
Read(f1,a1);
If not EOF(f1) then
Write(f,tmp,' ')
else
Write(f,tmp);
End;
While not EOF(f2) do
begin
tmp:=a2;
Read(f2,a2);
If not EOF(f2) then
Write(f,tmp,' ')
else
Write(f,tmp);
End;
Close(f); Close(f1); Close(f2);
End;
Erase(f1);
Erase(f2);
End;
Delphi (сортировка произвольных типов данных - простое слияние)
unit uMergeSort;
interface
type
TItem = Integer; //Здесь можно написать Ваш произвольный тип
TArray = array of TItem;
procedure MergeSort(var Arr: TArray);
implementation
function IsBigger(d1, d2 : TItem) : Boolean;
begin
Result := (d1 > d2); //Сравниваем d1 и d2. Не обязательно так. Зависит от Вашего типа.
//Сюда можно добавить счетчик сравнений
end;
//Процедура сортировки слияниями
procedure MergeSort(var Arr: TArray);
var
tmp : TArray; //Временный буфер // А где реализация процедуры? Этот код работать не будет, допишите, пожалуйста
//Слияние
procedure merge(L, Spl, R : Integer);
var
i, j, k : Integer;
begin
i := L;
j := Spl + 1;
k := 0;
//Выбираем меньший из первых и добавляем в tmp
while (i <= Spl) and (j <=R) do
begin
if IsBigger(Arr[i], Arr[j]) then
begin
tmp[k] := Arr[j];
Inc(j);
end
else
begin
tmp[k] := Arr[i];
Inc(i);
end;
Inc(k);
end;
//Просто дописываем в tmp оставшиеся эл-ты
if i <= Spl then //Если первая часть не пуста
for j := i to Spl do
begin
tmp[k] := Arr[j];
Inc(k);
end
else //Если вторая часть не пуста
for i := j to R do
begin
tmp[k] := Arr[i];
Inc(k);
end;
//Перемещаем из tmp в arr
Move(tmp[0], Arr[L], k*SizeOf(TItem));
end;
//Сортировка
procedure sort(L, R : Integer);
var
splitter : Integer;
begin
//Массив из 1-го эл-та упорядочен по определению
if L >= R then Exit;
splitter := (L + R) div 2; //Делим массив пополам
sort(L, splitter); //Сортируем каждую
sort(splitter + 1, R); //часть по отдельности
merge(L, splitter, R); //Производим слияние
end;
//Основная часть процедуры сортировки
begin
SetLength(tmp, Length(Arr));
sort(0, Length(Arr) - 1);
SetLength(tmp, 0);
end;
end.
D
void mergeSort(int[] array) {
static void merge(int[] array, int q) {
int[] leftArray = array[0..q].dup ~ int.max;
int[] rightArray = array[q..$].dup ~ int.max;
int i = 0;
int j = 0;
int length = array.length;
for (int k = 0; k < length; ++k) {
array[k] = (leftArray[i] <= rightArray[j]) ? leftArray[i++] : rightArray[j++];
}
}
if (array.length > 1) {
int q = array.length / 2;
mergeSort(array[0..q]);
mergeSort(array[q..$]);
merge(array, q);
}
}