Методы сортировок массивов

                        Содержание.

 

Введение

 

1. Метод "Пузырька".

2. Метод Шелла.

3. Обменная сортировка с разделением (Quicksort).

4.  Сортировка перемешиванием (Шейкерная сортировка) (англ. Cocktail sort).

5. Гномья сортировка (англ. Gnome sort).

6. Сортировка вставками  — простой алгоритм сортировки.

7. Блочная сортировка.

8. Сортировка подсчётом.

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

10. Сортировка с помощью  двоичного дерева.

11.Сортировка выбором.

12. Пирамидальная сортировка (англ. Heapsort) .

13. Быстрая сортировка.

 

Заключение.

 

Источники информации.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                          Введение.

 

 

Основными операциями, выполняемыми над массивами, являются упорядочение (сортировка) записей и поиск в массиве записи по заданному условию( по ключу ). Сортировка является операцией расстановки записей массива в определенном порядке в соответствии с некоторым критерием упорядочения. Сортировка осуществляется в соответствии со значением ключей всех записей (напр., упорядочение фамилий по алфавиту или чисел по возрастанию ). Существует достаточно много методов сортировки, принципиально отличающихся друг от друга. Если массив целиком помещается в оперативной памяти ЭВМ, то его упорядочение называют внутренним. Если для хранения упорядочиваемых данных используются внешнее запоминающее устройство, то такое упорядочение называют внешним. Критериями оценки методов сортировки являются:

  С -   количество  операций сравнения пар ключей,

  Р -   число перестановок  элементов ,

  S -   резерв памяти.

Среднее количество операций   сравнения зависит от   метода сортировки и при рациональном выборе метода достигает некоторого минимума, зависящего от n - размера массива (размер массива - количество содержащихся в нём записей). Методы внутренней сортировки можно разделить на две группы:

-   методы, не требующие  резерва памяти;

-   методы, требующие  резерва памяти.

К первой группе относятся такие методы, как метод выборки, "пузырька", вставки, Шелла. Ко второй группе относятся метод квадратичной выборки,   метод слияния и другие. Простые методы сортировки (выбором, обменом, вставкой) требуют приблизительно n**2 сравнений. Более сложные алгоритмы обычно обеспечивают получение результата за n*log2(n) сравнений в среднем: сортировка методом Шелла, слиянием, "быстрая сортировка". Однако оптимальной в любом случае сортировки не существует, так как их эффективность существенно зависит от типа ключей в массиве и их предварительной упорядоченности.

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1.   Метод "Пузырька".

При использовании этого способа требуется самое большее (n-1) проходов. В течение первого прохода массива сравниваются ключи К1 и К2 первой и второй записей, и, если порядок между ними нарушен,   то записи R1 и R2 меняются местами. Затем этот процесс повторяется для записей R2 и R3, R3 и R4 и т.д. Данный метод заставляет двигаться, или "всплывать", записи с малыми ключами.   После первого прохода запись с наибольшим   ключом будет находиться на n - й позиции массива. При каждом последующем проходе записи со следующем наибольшим ключом будут располагаться в позициях n-1,   n-2, ... , 2      соответственно, в результате чего будет сформирована отсортированная таблица. После каждого прохода через массив может быть сделана проверка, были ли совершены перестановки в течение данного прохода. Если перестановок не было, то это означает, что массив уже отсортирован и дальнейших проходов не требуется. Кроме того, можно запоминать индекс последней перестановки. Это позволит уменьшить на следующем шаге просматриваемый массив.

  Характеристики сортировки методом "пузырька" в худшем случае составляют n(n-1)/2 сравнений и n(n-1)/2 перестановок (худшим считается случай,когда элементы наиболее удалены от своих конечных позиций). Среднее число сравнений и перестановок имеет порядок n**2 . Сортировка пузырьковым методом использует метод обменной  сортировки. Она основана на выполнении в цикле операций сравнения и при необходимости обмена соседних элементов. Ее название происходит из-за подобия процессу движения пузырьков в резервуаре с  водой когда каждый пузырек находит свой собственный уровень.

Сортировку пузырьковым методом можно в   некоторой степени   улучшить и тем самым немного улучшить ее временные характеристики. Можно, например, заметить, что сортировка пузырьковым методом обладает одной особенностью: расположенный не на своем месте в  конце массива элемент (например, элемент "а" в массиве "dcab")  достигает своего места за один проход, а элемент, расположенный в начале массива (например, элемент "d"), очень медленно достигает своего места.   Необязательно все просмотры делать в одном направлении. Вместо этого всякий последующий просмотр можно делать в противоположном направлении.   В этом случае сильно удаленные от своего места элементы будут быстро перемещаться в соответствующее место. Хотя эта сортировка является улучшением пузырьковым методом,  ее нельзя рекомендовать для использования, поскольку время выполнения по-прежнему зависит квадратично от числа элементов. Число сравнений не изменяется, а число обменов уменьшается лишь на незначительную величину.

2.   Метод Шелла.

Алгоритм сортировки, являющийся усовершенствованным вариантом сортировки вставками. Идея метода Шелла состоит в сравнении элементов, стоящих не только рядом, но и на определённом расстоянии друг от друга. Иными словами — это сортировка вставками с предварительными «грубыми» проходами. Аналогичный метод усовершенствования пузырьковой сортировки называется сортировка расчёской.

Описание

При сортировке Шелла сначала сравниваются и сортируются между собой значения, отстоящие один от другого на некотором расстоянии d (о выборе значения d см. ниже). После этого процедура повторяется для некоторых меньших значений d, а завершается сортировка Шелла упорядочиванием элементов при d = 1 (то есть, обычной сортировкой вставками). Эффективность сортировки Шелла в определённых случаях обеспечивается тем, что элементы «быстрее» встают на свои места (в простых методах сортировки, например, пузырьковой, каждая перестановка двух элементов уменьшает количество инверсий в списке максимум на 1, а при сортировке Шелла это число может быть больше).

Невзирая на то, что сортировка Шелла во многих случаях медленнее, чем быстрая сортировка, она имеет ряд преимуществ:

отсутствие потребности в памяти под стек;

отсутствие деградации при неудачных наборах данных — быстрая сортировка легко деградирует до O(n²), что хуже, чем худшее гарантированное время для сортировки Шелла.

Общий метод, который использует сортировку вставкой, применяет принцип уменьшения расстояния между сравниваемыми элементами. Сначала сортируются все элементы, которые смещены  друг от друга на три позиции. Затем сортируются все элементы, которые смещены на две позиции. И, наконец, упорядочиваются все соседние элементы.

При поверхностном взгляде на алгоритм нельзя сказать, что он  дает хороший результат и даже то, что в результате получится отсортированный массив.   Однако, он дает и то и другое. Эффективность этого алгоритма объясняется тем, что при каждом проходе используется относительно небольшое число элементов или элементы  массива уже находятся в относительном порядке, а упорядоченность увеличивается при каждом новом просмотре данных.

Расстояния между сравниваемыми элементами могут изменяться  по-разному. Обязательным является лишь то, что последний шаг должен равняться единице. Например, хорошие результаты дает последовательность шагов 9, 5, 3, 2, 1,. Следует избегать последовательностей степени  двойки, которые, как показывают сложные математические выкладки, снижают эффективность алгоритма сортировки. /Однако, при использовании таких последовательностей шагов между сравниваемыми элементами эта сортировка будет по-прежнему работать правильно. Слегка измененные версии сортировки Шелла используют специальные управляющие элементы, которые не являются в действительности частью той информации, которая  должна сортироваться. Управляющие элементы имеют граничные для массива данных значения, т.е. наименьшее и наибольшее значения. В  этом случае не обязательно выполнять проверку на граничные значения. Однако, применение таких управляющих элементов требует специальных знаний о той информации, которая сортируется, и это снижает универсальность процедуры сортировки. Анализ сортировки Шелл требует решения некоторых сложных математических задач. Время  выполнения сортировки   Шелла пропорционально n**1.2. Эта зависимость значительно лучше квадратичной зависимости, которой подчиняются рассмотренные ранее алгоритмы сортировки. Однако, прежде чем вы решите использовать сортировку Шелла, следует иметь в виду, что быстрая сортировка дает даже еще лучшие результаты.

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

   h1=[n/2], а hi=h((i-1)/2).

В более поздних работах Хиббард показал, что для ускорения процесса целесообразно определить шаг h1 по формуле:

h1=2**k+1 , где 2**k < n <= 2**(k+1).

После выбора h1 методом вставки упорядочиваются группы, содержащие элементы с номерами позиций

i, i+h1, i+2*h1, ..., i+mi*h1.

При этом i=1,2,...,h1; m[i] - наибольшее целое, удовлетворяющее неравенству i+m[i]*hi <= n.

Затем выбирается шаг h2<h1 и упорядочиваются группы, содержащие элементы с номерами позиций i, i+h2, ..., i+m[i]*h2. Эта процедура со все уменьшающимися шагами продолжается до тех пор, пока очередной шаг h[l] станет равным единице (h1>h2>...>hl). Этот последний этап представляет собой упорядочение всего массива методом вставки. Но так как исходный массив упорядочивался отдельными группами с последовательным объединением этих групп, то общее количество сравнений значительно меньше, чем n /4, требуемое при методе вставки. Число операций сравнения пропорционально n*(log2(n))**2 .

Пример,

Пусть дан список A = (32,95,16,82,24,66,35,19,75,54,40,43,93,68) и выполняется его сортировка методом Шелла, а в качестве значений d выбраны 5,3,1.

На первом шаге сортируются подсписки A, составленные из всех элементов A, различающихся на 5 позиций, то есть подсписки A5,1 = (32,66,40), A5,2 = (95,35,43), A5,3 = (16,19,93), A5,4 = (82,75,68), A5,5 = (24,54).

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

Процесс завершается обычной сортировкой вставками получившегося списка.

3.   Обменная сортировка с разделением (Quicksort).

Данный метод является одним из лучших методов внутренней сортировки и весьма эффективен для больших массивов. Целью каждого шага в данном методе является помещение очередной рассматриваемой записи на конечную позицию внутри массива. Если поступать таким способом, то все записи, предшествующие данной, будут иметь меньший ключ, в то время как все последующие - больший. При использовании такого метода массив всегда делится на два подмассива. Анологичный процесс может быть применен к каждому из этих подмассивов и повторяться до тех пор, пока все записи не будут установлены на их конечные позиции. Используются два индекса i и j с начальными значениями границ массива. Сравниваются ключи K[i] и K[j], и если перестановка не требуется, то j уменьшается на 1, и процесс повторяется. В том   случае, когда K[i]>=K[j], записи R[i] и R[j] меняются местами. Затем этот процесс повторяется с i, увеличенным на 1, и фиксированным j до тех пор, пока не возникает другая перестановка. В этот момент j снова будет уменьшено на 1, а i останется фиксированным, и т.д. Процесс выполняется до тех пор, пока i<j.

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

Разделение следует применять для подмассивов, длина которых больше 9, а короткие подмассивы упорядочивать методом вставки.

Стек занимает мало места. Например, стек из 20 строк позволяет упорядочить массив, содержащую до 10**7 записей. Кроме того, в современных языках программирования   при работе рекурсивных программ занесение и извлечение из стека выполняется автоматически, поэтому рекомендуется использовать именно этот механизм. Среднее число сравнений для данного алгоритма составляет n*log(n) где n - число записей в сортируемом массиве, m - размер подмассива, сортируемой методом вставки.

Наихудшей ситуацией при использовании рассмотренного алгоритма является случай, когда массив уже отсортирован. При этом число сравнений порядка n, т.е. алгоритм не лучше сортировки выборкой.

4. Сортировка перемешиванием (Шейкерная сортировка) (англ. Cocktail sort) .

Разновидность пузырьковой сортировки. Анализируя метод пузырьковой сортировки можно отметить два обстоятельства.

Во-первых, если при движении по части массива перестановки не происходят, то эта часть массива уже отсортирована и, следовательно, ее можно исключить из рассмотрения.

Во-вторых, при движении от конца массива к началу минимальный элемент “всплывает” на первую позицию, а максимальный элемент сдвигается только на одну позицию вправо.

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

Лучший случай для этой сортировки — отсортированный массив (О(n)), худший — отсортированный в обратном порядке (O(n²)).

5.Гномья сортировка (англ. Gnome sort) .

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

 Гномья сортировка  основана на технике, используемой  обычным голландским садовым  гномом (нидерл. tuinkabouter). Это метод, которым  садовый гном сортирует линию  цветочных горшков. По существу  он смотрит на следующий и  предыдущий садовые горшки: если  они в правильном порядке, он  шагает на один горшок вперёд, иначе он меняет их местами  и шагает на один горшок  назад. Граничные условия: если нет  предыдущего горшка, он шагает  вперёд; если нет следующего горшка, он закончил.

Дик Грун

Алгоритм концептуально простой, не требует вложенных циклов. Время работы . На практике алгоритм может работать так же быстро, как и сортировка вставками.

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

Описание

Ниже написан псевдокод сортировки. Это оптимизированная версия с использованием переменной j, чтобы разрешить прыжок вперёд туда, где он остановился до движения влево, избегая лишние итерации и сравнения:

gnomeSort(a[0..size - 1])

i = 1;

j = 2;

while i < size

if a[i - 1] <= a[i] //для сортировки  по убыванию поменяйте знак  сравнения на >=

i = j;

j = j + 1;

else

swap a[i - 1] and a[i]

i = i - 1;

if i == 0

i = j;

j = j + 1;

Пример:

Если мы хотим отсортировать массив с элементами [4] [2] [7] [3] от большего к меньшему, то на итерациях цикла while будет происходить следующее:

[4] [2] [7] [3] (начальное состояние: i == 1, j == 2);

[4] [2] [7] [3] (ничего не произошло, но сейчас i == 2, j == 3);

[4] [7] [2] [3] (обмен a[2] и a[1], сейчас i == 1, а j == 3 по-прежнему);

[7] [4] [2] [3] (обмен a[1] и a[0], сейчас i == 3, j == 4);

[7] [4] [3] [2] (обмен a[3] и a[2], сейчас i == 2, j == 4);

[7] [4] [3] [2] (ничего не произошло, но сейчас i == 4, j == 5);

цикл закончился, т. к. i не < 4.

 

6.Сортировка вставками — простой алгоритм сортировки.

Хотя этот алгоритм сортировки уступает в эффективности более сложным (таким как быстрая сортировка), у него есть ряд преимуществ:

эффективен на небольших наборах данных, на наборах данных до десятков элементов может оказаться лучшим;

эффективен на наборах данных, которые уже частично отсортированы;

это устойчивый алгоритм сортировки (не меняет порядок элементов, которые уже отсортированы);

может сортировать список по мере его получения;

не требует временной памяти, даже под стек.

Минусом же является высокая сложность алгоритма: O(n²).

Описание

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

Анализ алгоритма

Время выполнения алгоритма зависит от входных данных: чем большее множество нужно отсортировать, тем большее время выполняется сортировка. Также на время выполнения влияет исходная упорядоченность массива. Так, лучшим случаем является отсортированный массив, а худшим — массив, отсортированный в порядке, обратном нужному. Временная сложность алгоритма при худшем варианте входных данных — θ(n²).

Псевдокод[1]

Вход: массив A, состоящий из элементов A[1], A[2], ..., A[n]

for i = 2, 3, ..., n:

key := A[i]

j := i - 1

while j > 0 and A[j] > key:

A[j + 1] := A[j]

j := j - 1

A[j + 1] := key

Реализация на С++[2]

void insertionSort(int arr[], int length) {

int i, j, tmp;

for (i = 1; i < length; i++) {

j = i;

while (j > 0 && arr[j - 1] > arr[j]) {

tmp = arr[j];

arr[j] = arr[j - 1];

arr[j - 1] = tmp;

j--;

}

}

}

7.Блочная сортировка .

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

Данный алгоритм требует знаний о природе сортируемых данных, выходящих за рамки функций "сравнить" и "поменять местами", достаточных для сортировки слиянием, сортировки пирамидой, быстрой сортировки, сортировки Шелла, сортировки вставкой.

Преимущества: относится к классу быстрых алгоритмов с линейным временем исполнения O(N) (на удачных входных данных).

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

Алгоритм

Если входные элементы подчиняются равномерному закону распределения, то математическое ожидание времени работы алгоритма карманной сортировки является линейным. Это возможно благодаря определенным предположениям о входных данных. При карманной сортировке предполагается, что входные данные равномерно распределены на отрезке [0, 1).

Идея алгоритма заключается в том, чтобы разбить интервал [0, 1) на n одинаковых отрезков (карманов), и разделить по этим карманам n входных величин. Поскольку входные числа равномерно распределены, предполагается, что в каждый карман попадет небольшое количество чисел. Затем последовательно сортируются числа в карманах. Отсортированный массив получается путем последовательного перечисления элементов каждого кармана.

Псевдокод

function bucket-sort(A, n) is

buckets ← новый массив  из n пустых элементов

for i = 0 to (length(A)-1) do

вставить A[i] в конец массива buckets[msbits(A[i], k)]

for i = 0 to n - 1 do

next-sort(buckets[i])

return Конкатенация массивов buckets[0], ..., buckets[n-1]

На вход функции bucket-sort подаются сортируемый массив (список, коллекция и т.п.) A и количество блоков - n.

Массив buckets представляет собой массив массивов (массив списков, массив коллекций и т.п.), подходящих по природе к элементам A.

Функция msbits(x,k) тесно связана с количеством блоков - n (возвращает значение от 0 до n), и, в общем случае, возвращает k наиболее значимых битов из x (floor(x/2^(size(x)-k))). В качестве msbits(x,k) может быть использованы разнообразные функции, подходящие к природе сортируемых данных и позволяющие разбить массив A на n блоков. Например, для символово A-Z это может быть сопоставление буквам чисел 0-25, или возврат кода первой буквы (0-255) для ASCII набора символов; для чисел [0, 1) это может быть функция floor(n*A[i]), а для произвольного набора чисел в интервале [a, b) - функция floor(n*(A[i]-a)/(b-a)).

Функция next-sort также реализует алгоритм сотрировки для каждого созданного на первом этапе блока. Рекурсивное использование bucket-sort в качестве next-sort превращает данный алгоритм в поразрядную сортировку. В случае n = 2 соответствует быстрой сортировке (хотя и с потенцильно плохим выбором опорного элемента).

8.Сортировка подсчётом .

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

Предположим, что входной массив состоит из n целых чисел в диапазоне от 0 до k − 1, где . Далее алгоритм будет обобщён для произвольного целочисленного диапазона. Существует несколько модификаций сортировки подсчётом, ниже рассмотрены три линейных и одна квадратичная, которая использует другой подход, но имеет то же название.

Это простейший вариант алгоритма. Создать вспомогательный массив C[0..k - 1], состоящий из нулей, затем последовательно прочитать элементы входного массива A, для каждого A[i] увеличить C[A[i]] на единицу. Теперь достаточно пройти по массиву C, для каждого в массив A последовательно записать число j C[j] раз.

SimpleCountingSort

for i = 0 to k - 1

C[i] = 0;

for i = 0 to n - 1

C[A[i]] = C[A[i]] + 1;

b = 0;

for j = 0 to k - 1

for i = 0 to C[j] - 1

A[b] = j;

b = b + 1;

 

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

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

Для решения задачи сортировки эти три этапа выглядят так:

Сортируемый массив разбивается на две части примерно одинакового размера;

Каждая из получившихся частей сортируется отдельно, например — тем же самым алгоритмом;

Два упорядоченных массива половинного размера соединяются в один.

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

Нетривиальным этапом является соединение двух упорядоченных массивов в один. Основную идею слияния двух отсортированных массивов можно объяснить на следующем примере. Пусть мы имеем две стопки карт, лежащих рубашками вниз так, что в любой момент мы видим верхнюю карту в каждой из этих стопок. Пусть также, карты в каждой из этих стопок идут сверху вниз в неубывающем порядке. Как сделать из этих стопок одну? На каждом шаге мы берём меньшую из двух верхних карт и кладём её (рубашкой вверх) в результирующую стопку. Когда одна из оставшихся стопок становится пустой, мы добавляем все оставшиеся карты второй стопки к результирующей стопке.

Псевдокод на C++-подобном языке:

L = *In1;

R = *In2;

if( L == R )

{

*Out++ = L;

In1++;

*Out++ = R;

In2++;

}

else if( L < R )

{

*Out++ = L;

In1++;

}

else

{

*Out++ = R;

In2++;

}

10.Сортировка с помощью двоичного дерева.

(сортировка двоичным  деревом, сортировка деревом, древесная  сортировка, сортировка с помощью  бинарного дерева, англ. tree sort) —  универсальный алгоритм сортировки, заключающийся в построении двоичного  дерева поиска по ключам массива (списка), с последующей сборкой  результирующего массива путём  обхода узлов построенного дерева  в необходимом порядке следования  ключей. Данная сортировка является  оптимальной при получении данных  путём непосредственного чтения  с потока (например с файла, сокета  или консоли).