Сортировка merge. Сортировка слиянием по-простому

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 (s0 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

Сортировка естественным слиянием

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

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, 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.dup ~ int.max; int rightArray = array.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 : rightArray; } } if (array.length > 1) { int q = array.length / 2; mergeSort(array); mergeSort(array); merge(array, q); } }

Python 2.7 (функциональная реализация)

Def merge(right, left, result): result.append((left if left < right else right).pop(0)) return merge(right=right, left=left, result=result) if left and right else result+left+right merge_sort = (lambda arr: arr if len(arr) == 1 else merge(merge_sort(arr), merge_sort(arr[:len(arr)/2]), ))

Недостатком сортировки слиянием является использование дополнительной памяти. Но когда работать приходиться с файлами или списками, доступ к которым осуществляется только последовательно, то очень удобно применять именно этот метод. Также, к достоинствам алгоритма стоит отнести его устойчивость и неплохую скорость работы O(n*logn).

При написании статьи были использованы открытые источники сети интернет:

Алгоритм сортировки слиянием был предложен праотцом современных компьютеров – Джоном фон Нейманом. Сам метод является устойчивым, т. е. он не меняет одинаковые по значению элементы в списке.

В основе сортировки слиянием лежит принцип «разделяй и властвуй». Список разделяется на равные или практически равные части, каждая из которых сортируется отдельно. После чего уже упорядоченные части сливаются воедино. Несколько детально этот процесс можно расписать так:

1. массив рекурсивно разбивается пополам, и каждая из половин делиться до тех пор, пока размер очередного подмассива не станет равным единице;

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

3. в конце операции слияния, элементы перезаписываются из результирующего массива в исходный.

Подпрограмма MergeSort рекурсивно разбивает и сортирует массив, а Merge отвечает за его слияние. Так можно записать псевдокод основной подпрограммы:

Подпрограмма MergeSort (A , first , last )

A – массив

first , last – номера первого и последнего элементов соответственно

Если first <last то

Вызов MergeSort (A , first , (first +last )/2) //сортировка левой части

Вызов MergeSort (A , (first +last )/2+1, last ) //сортировка правой части

Вызов Merge (A , first , last ) //слияние двух частей

Эта подпрограмма выполняется только в том случае, если номер первого элемента меньше номера последнего. Как уже говорилось, из подпрограммы MergeSort вызывается подпрограмма Merge , которая выполняет операцию слияния. Перейдем к рассмотрению последней.

Работа Merge заключается в образовании упорядоченного результирующего массива путем слияния двух также отсортированных массивов меньших размеров. Вот псевдокод этой подпрограммы:

Подпрограмма Merge (A , first , last )

start , final – номера первых элементов левой и правой частей

mas – массив, middle - хранит номер среднего элемента

middle =(first+last)/2 //вычисление среднего элемента

start =first //начало левой части

final =middle +1 //начало правой части

Цикл j =first до last выполнять //выполнять от начала до конца

Если ((start <=middle ) и ((final >last ) или (A [start ]<A [final ]))) то

mas [j ]=A [start ]

увеличить start на 1

mas [j ]=A [final ]

увеличить final на 1

Цикл j =first до last выполнять //возвращение результата в список

A [j ]=mas [j ]

Разберем алгоритм сортировки слиянием на следующем примере (рис. 6.10). Имеется неупорядоченная последовательность чисел: 2, 6, 7, 1, 3, 5, 0, 4. После разбивки данной последовательности на единичные массивы, процесс сортирующего слияния (по возрастанию) будет выглядеть так:

Рисунок 6.10 – Пример сортировки слиянием

Массив был разделен на единичные массивы, которые алгоритм сливает попарно до тех пор, пока не получится один массив, все элементы которого стоят на своих позициях.

Код программы на C++:

void Merge(int *A, int first, int last) //функция, сливающая массивы

int middle, start, final, j;

int *mas=new int;

middle=(first+last)/2; //вычисление среднего элемента

start=first; //начало левой части

final=middle+1; //начало правой части

for(j=first; j<=last; j++) //выполнять от начала до конца

if ((start<=middle) && ((final>last) || (A

mas[j]=A;

mas[j]=A;

for (j=first; j<=last; j++) A[j]=mas[j]; //возвращение результата в список

void MergeSort(int *A, int first, int last) //рекурсивная процедура сортировки

if (first

MergeSort(A, first, (first+last)/2); //сортировка левой части

MergeSort(A, (first+last)/2+1, last); //сортировка правой части

Merge(A, first, last); //слияние двух частей

void main() //главная функция

cout<<"Размер массива > "; cin>>n;

for (i=1; i<=n; i++)

cout< ";

MergeSort(A, 1, n); //вызов сортирующей процедуры

cout<<"Упорядоченный массив: "; //вывод упорядоченного массива

for (i=1; i<=n; i++) cout<

Код программы на Pascal:

type massiv=array of integer;

var n, i: integer;

procedure Merge(var A: massiv; first, last: integer); {процедура, сливающая массивы}

var middle, start, final , j: integer;

middle:=(first+last) div 2; {вычисление среднего элемента}

start:=first; {начало левой части}

final:=middle+1; {начало правой части}

for j:=first to last do {выполнять от начала до конца}

if (start<=middle) and ((final>last) or (A

mas[j]:=A;

mas[j]:=A;

for j:=first to last do A[j]:=mas[j]; {возвращение результата в массив}

procedure MergeSort(var A: massiv; first, last: integer); {рекурсивная процедура сортировки}

if first

MergeSort(A, first, (first+last) div 2); {сортировка левой части}

MergeSort(A, (first+last) div 2+1, last); {сортировка правой части}

Merge(A, first, last); {слияние двух частей}

begin {основной блок программы}

write("Размер массива > ");

for i:=1 to n do

write(i, " элемент > ");

MergeSort(A, 1, n); {вызов сортирующей процедуры}

write("Упорядоченный массив: "); {вывод отсортированного массива}

for i:=1 to n do write(A[i], " ");

Недостатком сортировки слиянием является использование дополнительной памяти. Но когда работать приходиться с файлами или списками, доступ к которым осуществляется только последовательно, то очень удобно применять именно этот метод. Также, к достоинствам алгоритма стоит отнести его устойчивость и неплохую скорость работы O (n *log n ).

Как мы уже видели на примере быстрой сортировки, большую часть рекурсивных алгоритмов можно усовершенствовать, обрабатывая файлы небольших размеров специальным образом. В силу рекурсивного характера функции часто вызываются именно для небольших файлов, поэтому улучшение их обработки приводит к улучшению всего алгоритма. Следовательно, как и для быстрой сортировки, переключение на сортировку вставками подфайлов небольших размеров даст улучшение времени выполнения типичной реализации сортировки слиянием на 10-15%.

Следующее полезное усовершенствование - это устранение времени копирования данных во вспомогательный массив, используемый слиянием. Для этого следует так организовать рекурсивные вызовы, что на каждом уровне процесс вычисления меняет ролями входной и вспомогательный массивы. Один из способов реализации такого подхода заключается в создании двух вариантов программ: одного для входных данных в массиве aux и выходных данных в массиве a, а другого - для входных данных в массиве a и выходных данных в массиве aux, обе эти версии поочередно вызывают одна другую. Другой подход продемонстрирован в программе 8.4, которая вначале создает копию входного массива, а затем использует программу 8.1 и переключает аргументы в рекурсивных вызовах, устраняя таким образом операцию явного копирования массива. Вместо нее программа поочередно переключается между выводом результата слияния то во вспомогательный, то во входной файл. (Это достаточно хитроумная программа.)

Программа 8.4. Сортировка слиянием без копирования

Данная рекурсивная программа сортирует массив b, помещая результат сортировки в массив a. Поэтому рекурсивные вызовы написаны так, что их результаты остаются в массиве b, а для их слияния в массив a используется программа 8.1. Таким образом, все пересылки данных выполняются во время слияний.

template void mergesortABr(Item a, Item b, int l, int r) { if (r-l <= 10) { insertion(a, l, r); return; } int m = (l+r)/2; mergesortABr(b, a, l, m); mergesortABr(b, a, m+1, r); mergeAB(a+l, b+l, m-l+1, b+m+1, r-m); } template void mergesortAB(Item a, int l, int r) { static Item aux; for (int i = l; i <= r; i++) aux[i] = a[i]; mergesortABr(a, aux, l, r); }

Данный метод позволяет избежать копирования массива ценой возвращения во внутренний цикл проверок исчерпания входных файлов. (Вспомните, что устранение этих проверок в программе 8.2 преобразовало этот файл во время копирования в бито-нический.) Положение можно восстановить с помощью рекурсивной реализации той же идеи: нужно реализовать две программы как слияния, так и сортировки слиянием: одну для вывода массива по возрастанию, а другую - для вывода массива по убыванию. Это позволяет снова использовать битоническую стратегию и устранить необходимость в сигнальных ключах во внутреннем цикле.

Поскольку при этом используются четыре копии базовых программ и закрученные рекурсивные переключения аргументов, такая супероптимизация может быть рекомендована только экспертам (ну или студентам), но все-таки она существенно ускоряет сортировку слиянием. Экспериментальные результаты, которые будут рассмотрены в разделе 8.6, показывают, что сочетание всех предложенных выше усовершенствований ускоряет сортировку слиянием процентов на 40, однако все же она процентов на 25 медленнее быстрой сортировки. Эти показатели зависят от реализации и от машины, но в разных ситуациях результаты похожи.

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

Упражнения

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

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

8.18. Предположим, программа 8.3 модифицирована так, что не вызывает метод merge при a[m] < a . Сколько сравнений экономится в этом случае, если сортируемый файл уже упорядочен?

8.19. Выполните модифицированный алгоритм, предложенный в упражнении 8.18, для больших случайно упорядоченных файлов. Экспериментально определите среднее количество пропусков вызова merge в зависимости от N (размер исходного сортируемого файла).

8.20. Допустим, что сортировка слиянием должна быть выполнена на h-сортированном файле для небольшого значения h. Какие изменения нужно внести в подпрограмму merge, чтобы воспользоваться этим свойством входных данных? Поэкспериментируйте с гибридами сортировки методом Шелла и сортировки слиянием, основанными на этой подпрограмме.

8.21. Разработайте реализацию слияния, уменьшающую требование дополнительной памяти до max(M, N/M) за счет следующей идеи. Разбейте массив на N/M блоков размером M (для простоты предположим, что N кратно M). Затем, (1) рассматривая эти блоки как записи, первые ключи которых являются ключами сортировки, отсортируйте их с помощью сортировки выбором, и (2) выполните проход по массиву, сливая первый блок со вторым, затем второй блок с третьим и так далее.

8.22. Докажите, что метод, описанный в упражнении 8.21, выполняется за линейное время.

8.23. Реализуйте битоническую сортировку слиянием без копирования.

Восходящая сортировка слиянием

Как было сказано в "Рекурсия и деревья" , у каждой рекурсивной программы имеется нерекурсивный аналог, который хотя и выполняет эквивалентные действия, но может делать это в другом порядке. Нерекурсивные реализации сортировки слиянием заслуживают детального изучения в качестве образцов философии алгоритмов " разделяй и властвуй " .

Рассмотрим последовательность слияний, выполняемую рекурсивным алгоритмом. Из примера, приведенного на рис. 8.2 , видно, что файл размером 15 сортируется следующей последовательностью слияний:

1-и-1 1-и-1 2-и-2 1-и-1 1-и-1 2-и-2 4-и-4

1-и-1 1-и-1 2-и-2 1-и-1 2-и-1 4-и-3 8-и-7.

Порядок выполнения слияний определяется рекурсивной структурой алгоритма. Но подфайлы обрабатываются независимо, поэтому слияния могут выполняться в различном порядке. На рис. 8.4 показана восходящая стратегия, при которой последовательность слияний такова:

1-и-1 1-и-1 1-и-1 1-и-1 1-и-1 1-и-1 1-и-1

2-и-2 2-и-2 2-и-2 2-и-1 4-и-4 4-и-3 8-и-7.

Рис. 8.4.

В каждой строке показан результат вызова метода merge при выполнении восходящей сортировки слиянием. Вначале выполняются слияния 1-и-1 : при слиянии A и S получается A S ; при слиянии O и R получается O R и т.д. Из-за нечетности размера файла последнее E не принимает участие в слиянии. На втором проходе выполняются слияния 2-и-2 : A S сливается с O R , и получается A O R S и т.д., до последнего слияния 2-и-1 . После этого выполняются слияния 4-и-4 , 4-и-3 и завершающее 8-и-7 .

В обоих случаях выполняются семь слияний 1-и-1 , три слияния 2-и-2 и по одному слиянию 2-и-1, 4-и-4, 4-и-3 и 8-и-7 , но они выполняются в различном порядке. Восходящая стратегия предлагает сливать наименьшие из оставшихся файлов, проходя по массиву слева направо.

Последовательность слияний, выполняемая рекурсивным алгоритмом, определяется деревом " разделяй и властвуй " , показанным на рис. 8.3 : мы просто выполняем обратный проход по этому дереву. Как было показано в "Элементарные структуры данных" , можно разработать нерекурсивный алгоритм, использующий явный стек, который даст ту же последовательность слияний. Однако совсем не обязательно ограничиваться только обратным порядком: любой проход по дереву, при котором обход поддеревьев узла завершается перед посещением самого узла, дает правильный алгоритм. Единственное ограничение заключается в том, что сливаемые файлы должны быть предварительно отсортированы. В случае сортировки слиянием удобно сначала выполнять все слияния 1-и-1 , затем все слияния 2-и-2 , затем все 4-и-4 , и так далее. Такая последовательность соответствует обходу дерева по уровням, который поднимается по дереву снизу вверх.

В "Рекурсия и деревья" мы уже видели на нескольких приме -рах, что при рассуждении в стиле снизу-вверх имеет смысл переориентировать мышление в сторону стратегии " объединяй и властвуй " , когда сначала решаются небольшие подзадачи, а затем они объединяются для получения решения большей задачи. В частности, нерекурсивный вариант вида " объединяй и властвуй " сортировки слиянием в программе 8.5 получается следующим образом: вначале все элементы файла рассматриваются как упорядоченные подсписки длиной 1. Потом для них выполняются слияния 1-и-1 , и получаются упорядоченные подсписки размером 2, затем выполняется серия слияний 2-и-2 , что дает упорядоченные подсписки размером 4, и так далее до упорядочения всего списка. Если размер файла не является степенью 2, то последний подсписок не всегда имеет тот же размер, что и все другие, но его все равно можно слить.

Если размер файла является степенью 2, то множество слияний, выполняемых восходящей сортировкой слиянием, в точности совпадает с множеством слияний, выполняемым рекурсивной сортировкой слиянием, однако последовательность слияний будет другой. Восходящая сортировка слиянием соответствует обходу дерева " разделяй и властвуй " по уровням, снизу вверх. В противоположность этому, рекурсивный алгоритм называется нисходящей сортировкой слиянием - в силу обратного обхода дерева сверху вниз.

Если размер файла не равен степени 2, восходящий алгоритм дает другое множество слияний, как показано на рис. 8.5 . Восходящий алгоритм соответствует дереву " объединяй и властвуй " (см. упражнение 5.75), отличному от дерева " разделяй и властвуй " , которое соответствует нисходящему алгоритму. Можно сделать так, чтобы последовательность слияний, выполняемых рекурсивным методом, была такой же, как и для нерекурсивного метода, однако для этого нет особых причин, поскольку разница в производительности невелика по отношению к общим затратам.

Если размер файла не равен степени 2, то структуры слияний для восходящей сортировки слиянием совершенно не похожи на структуры слияний для нисходящей сортировки ( рис. 8.3). При восходящей сортировке размеры всех файлов (возможно, за исключением последнего) равны степени 2. Эти различия помогают понять базовую структуру алгоритмов, но почти не влияют на производительность.

Леммы 8.1-8.4 справедливы и для восходящей сортировки слиянием, при этом имеют место следующие дополнительные леммы:

Лемма 8.5. Все слияния на каждом проходе восходящей сортировки слиянием манипулируют файлами, размер которых равен степени 2, за исключением, возможно, размера последнего файла.

Это факт легко доказать методом индукции.

Лемма 8.6. Количество проходов при восходящей сортировке слиянием по файлу из N элементов в точности равно числу битов в двоичном представлении N (без ведущих нулей). Размер подсписков после к проходов равен 2 k , т.к. на каждом проходе восходящей сортировки слиянием размер упорядоченных подфайлов удваивается. Значит, количество проходов, необходимое для сортировки файла из N элементов, есть наименьшее к такое, что , что в точности равно , т.е. количеству битов в двоичном представлении N. Этот результат можно доказать и методом индукции или с помощью анализа структурных свойств деревьев " объединяй и властвуй " . ¦

Программа 8.5. Восходящая сортировка слиянием

Восходящая сортировка слиянием состоит из последовательности проходов по всему файлу с выполнением слияний вида m-и-m и с удвоением m на каждом проходе. Последний подфайл имеет размер m лишь тогда, когда размер файла является четным кратным m, так что последнее слияние имеет тип m-и-х , для некоторого х, меньшего или равного m.

Подводя итоги, отметим, что нисходящая и восходящая сортировки - это два простых алгоритма сортировки, основанных на операции слияния двух упорядоченных подфайлов в результирующий объединенный упорядоченный файл. Оба алгоритма тесно связаны между собой и даже выполняют одно и то же множество слияний, если размер исходного файла является степенью 2, но они отнюдь не идентичны. На рис. 8.7 демонстрируются различия динамических характеристик алгоритмов на примере большого файла. Каждый алгоритм может использоваться на практике, если экономия памяти не важна, и желательно гарантированное время выполнения в худшем случае. Оба алгоритма представляют интерес как прототипы общих принципов построения алгоритмов: " разделяй и властвуй " и " объединяй и властвуй " .

Восходящая сортировка слиянием (слева) выполняет серию проходов по файлу, которые сливают упорядоченные подфайлы, пока не останется только один. Каждый элемент файла, за исключением, возможно, последнего, участвует в каждом проходе. В отличие от этого, нисходящая сортировка слиянием (справа) вначале упорядочивает первую половину файла, а затем берется за вторую половину (рекурсивно), поэтому диаграмма ее работы существенно отличается.

Упражнения

8.24. Покажите, какие слияния выполняет восходящая сортировка слиянием (программа 8.5) для ключей E A S Y Q U E S T I O N .

8.25. Реализуйте восходящую сортировку слиянием, которая начинает с сортировки вставками блоков по M элементов. Определите эмпирическим путем значение M, для которого разработанная программа быстрее всего сортирует произвольно упорядоченные файлы из N элементов, при N = 10 3 , 10 4 , 10 5 и 10 6 .

8.26. Нарисуйте деревья, которые отображают слияния, выполняемые программой 8.5 для N = 16, 24, 31, 32, 33 и 39 .

8.27. Напишите программу рекурсивной сортировки слиянием, выполняющую те же слияния, что и восходящая сортировка слиянием.

8.28. Напишите программу восходящей сортировки слиянием, выполняющую те же слияния, что и нисходящая сортировка слиянием. (Это упражнение намного труднее, чем упражнение 8.27).

8.29. Предположим, что размер файла является степенью 2. Удалите рекурсию из нисходящей сортировки слиянием так, чтобы получить нерекурсивную сортировку слиянием, выполняющую ту же последовательность слияний.

8.30. Докажите, что количество проходов, выполняемых нисходящей сортировкой слиянием, также равно количеству битов в двоичном представлении числа N (см. лемму 8.6).