[Играет музыка] 

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

Основная идея слияния сортировки для сортировки мелких массивов а затем объединить эти массивы вместе, или объединить them-- следовательно name-- в отсортированном порядке. Таким образом, что сортировка слиянием делает это, используя инструмент называется рекурсия, что и мы будем говорить о в ближайшее время, но мы не говорили о еще. 

Вот основная идея сортировки слиянием. Сортировать левую половину массива, при условии, N больше 1. И то, что я имею в виду, когда говорю, при условии, N больше, чем 1, Я думаю, что мы можем согласиться, что, если массив состоит только из одного элемента, это сортируется. Мы не на самом деле нужно чтобы сделать что-нибудь с ним. Мы можем просто объявить его быть отсортированы. Это всего лишь один элемент. 

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

Но помните, что пока массив является единственным элементом, мы можем объявить его сортировать. Тогда мы можем просто объединить их вместе. И это на самом деле Основная идея позади сортировки слиянием, это разбить его таким образом, что Ваши массивы имеют размер одного. И тогда вы восстановить оттуда. 

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

Итак, мы имеем тот же массив в качестве другие алгоритм сортировки видео если вы видели them-- Массив шесть элемент. И наша псевдокод здесь код является своего рода левая половина, сортировать правую половину, объединить две половинки вместе. Итак, давайте это очень темно красный кирпич массива и отсортировать левую половину. 

Так на данный момент, мы собираемся игнорировать вещи справа. Это там, но мы не на этом шаге еще. Мы не Сортировка Правая половина массива. Мы в то левого половина массива. И только ради быть немного более ясно, так что я могу обратиться на то, что шаг мы на, Я собираюсь переключить Цвет этого набора апельсина. Теперь, мы все еще говорим о же левая половина исходного массива. Но я надеюсь, что, будучи в состоянии см цвета различных предметов, это сделает его немного более ясно, что здесь происходит. 

ОК, так что теперь у нас есть три элемента массива. Как мы сортируем левую половину этого Массив, который до сих пор этот шаг? Мы пытаемся, чтобы отсортировать левую половина из красного кирпича array-- левая половина которого Я теперь окрашены в оранжевый цвет. 

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

И поэтому я хочу сказать, что левая половина левой половине массива это просто элемент пять. Пять, будучи один элемент Массив, мы знаем, как разбираться. И так пять сортируется. Мы просто заявить, что. Это один элемент массива. 

Таким образом, мы в настоящее время сортируются левая половина левой half-- вернее, мы отсортированы левая половина апельсина. Так что теперь, для того, чтобы по-прежнему полная левая половина общего массива, мы должны разобраться в правую половину апельсина, или этот материал. Как мы это делаем? Ну, у нас есть массив из двух элементов. Таким образом, мы можем отсортировать левую половину массива, который два. Два это единственный элемент. Так что это сортируется по умолчанию. Тогда мы можем отсортировать правую половину той части массива, один. Это своего рода по умолчанию. 

Теперь это в первый раз мы достигли шаг слияния. Мы завершили, хотя мы теперь вид вложенных down-- и это своего рода хитрый что с рекурсии, Вы должны держать голову о том, где мы находимся. Таким образом, мы своего рода слева половина оранжевого части. 

И теперь, мы находимся в середине сортировки правая половина оранжевого части. И в этом процессе, мы теперь собирается быть на шаг, объединить две половинки вместе. Когда мы смотрим на две половины массива, мы видим два и один. Какой элемент меньше? Один. 

Тогда, какой элемент меньше? Ну, это два или ничего. Так что это два. Так что теперь, просто снова кадр где мы находимся в контексте мы сортируются левая половина апельсина а правая половина происхождения. Я знаю, что я изменил цвета снова, но это, где мы были. И причина Я сделал это в том, что этот процесс продолжать идти, повторяя вниз. Мы отсортировали левый половина бывшего оранжевого а правая половина прежнего оранжевого цвета. 

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

Левая половина, наименьший элемент на левой половине пять. Наименьшее элемент на правая половина является одним. Какой из них является меньше? Один. 

Наименьшее элемент на левая половина пять. Наименьшее элемент на правая половина это два. Что наименьшее? Два. И тогда, наконец, пять ничего, мы можем сказать, пять. 

Итак, картина, давайте перерыв на секунду и выяснить, где мы находимся. Если бы мы начали с в самом начале, мы Теперь завершены общая массив только один шаг кода псевдокода здесь. Мы сортируются левая половина массива. 

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

Так что теперь давайте заморозить там. А теперь давайте разберёмся право половина исходного массива. И мы собираемся сделать это, переживает то же самое итеративный процесс разрушения вещи вниз , а затем объединять их вместе. 

Таким образом, левая половина из красный или левая половина правой половины первоначального Массив, я собираюсь сказать, три. Опять же, я здесь быть последовательным. Если у вас есть нечетное Количество элементов, его на самом деле не имеет значения, Вы делаете левая меньше или право поменьше. 

Важно то, что всякий раз, когда вам столкнулись с этой проблемой в проведении слияние, вам нужно быть последовательным. Вы либо должны всегда сделать левая сторона меньше или всегда нужно сделать правая сторона меньше. Здесь я выбрал, чтобы всегда сделать левая сторона меньше когда мой массив, или мой суб-массива, является нечетной размера. 

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

Опять же, мы должны разделить это вниз. Это не единственный элемент массива. Мы не можем объявить его сортировать. И так во-первых, мы собираемся сортировать левую половину. 

Левая половина один элемент, так что это своего рода по умолчанию. Тогда мы идем, чтобы отсортировать право половина, что один элемент. Это сортируются по умолчанию. И сейчас, мы можем объединить эти два вместе. Четыре меньше, и затем шесть меньше. 

Опять же, то, что мы сделали в этот момент? Мы отсортировали левый половина правой половине. Или вернуться к оригиналу цвета, которые были там, мы отсортировали левый половина мягкого красного. Первоначально он был темно-кирпич красный и теперь это мягче красный, или это была мягче красный. 

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

Так что теперь мы можем объединить тех, две половинки вместе. И это то, что мы делаем здесь. Так черной линии только разделить левую половину а правая половина этого рода части. 

Мы сравниваем наименьшее значение на левой стороне array-- или, простите, наименьшая Значение левой половине наименьшему значению права половина и обнаружили, что три меньше. А теперь немного оптимизации, верно? Там самом деле ничего оставили на левой стороне. 

Там нет ничего остальные с левой стороны, поэтому мы можем эффективно просто move-- мы можем объявить остальное на самом деле сортируются и только лавировать его на, потому что нет ничего еще для сравнения. И мы знаем, что правая сторона с правой стороны сортируется. 

ОК, так что теперь давайте снова и заморозить выяснить, где мы находимся в истории. В общем массиве, Что мы сделали? Мы на самом деле выполнить Теперь шаги одно и второй этап. Мы отсортировали левую половину, и мы отсортировали правую половину. 

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

Два меньше трех, так что два идет. Три менее чем 5, так три идет. Четыре меньше, чем 5, так четверка заходит. Тогда пять меньше, чем шесть, и шесть это все, что остается. 

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

Но на самом деле, потому что Многие из этих процессов происходят в то же time-- что то, что мы будем, опять же, говорить, когда мы говорим о рекурсия в будущем video-- этот алгоритм на самом деле ясно принципиально отличается от всего, мы видели раньше но также значительно более эффективным. 

Почему это? Ну, в худшем сценарий, у нас есть разделить п элементов до а затем сливают. Но когда мы воссоединить им, что мы делаем в основном удвоение Размер меньших массивов. У нас есть куча одного элемента массивы, которые мы эффективно объединить в двух массивах элементов. А потом мы возьмем тех, два массива элемент и объединить их вместе в четыре массива элементов, и так далее, не и так далее, и так далее, до тех пор, есть один массив п элементов. 

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

Так что какая-то логарифмическая элементом здесь. Но мы также все еще есть, по крайней мере смотреть на все п элементов. Таким образом, в худшем случае, сортировка слиянием работает в п журнала п. Мы должны смотреть на все п элементов, и мы должны объединить их вместе в журнале н наборов шагов. В лучшем случае, массив прекрасно отсортированы. Замечательно. Но на основе алгоритма мы имеем здесь, мы все еще должны разделить, а затем. Хотя в этом случае рекомбинирующий вроде неэффективными. Она не нужна. Но мы по-прежнему идти через весь процесс в любом случае. 

Таким образом, в лучшем случае а в худшем случае, этот алгоритм работает в журнале н н времени. Слияние рода, безусловно, немного сложнее чем других основных алгоритмов сортировки мы говорили о CS50, но существенно более мощным. 

И поэтому, если вы когда-нибудь найти Поводом для это нужно или использовать его для сортировки большой набор данных, получение Ваша голова вокруг идеи рекурсии будет очень мощный. И это будет сделать свой программы действительно намного эффективнее с помощью сортировка слиянием против что-нибудь еще. Я Дуг Ллойд. Это CS50.