[音乐播放] 

DOUG LLOYD：OK，这样的合并 排序是另一种算法 我们可以用它来梳理 数组的元素。 但是，正如我们看到的，它有一个 很根本的区别 从选择排序，冒泡 排序和插入排序 这使得它真的很聪明。 

合并背后的基本理念 排序是更小的数组排序 然后再结合这些阵列 在一起，或合并them-- 因此，在有序的name--。 该归并排序的方式做 这是通过利用一个工具 被称为递归，这是什么 我们要谈论不久， 但我们还没有真正谈过呢。 

这里的背后归并排序的基本思想。 对数组进行排序的左半部分， 假设n大于1。 而我的意思是，当我说 假设n大于1是 我想我们可以同意，如果一个数组 仅由一个单一的元件的， 它的排序。 我们实际上并不需要 做任何事情来了。 我们只需将其声明进行排序。 这只是一个单一的元件。 

这样的伪码，同样，是 对数组进行排序的左一半， 然后排序右半阵列， 然后合并两半。 现在，已经你可能会 思考，它只是一种 听起来你推迟喜欢the-- 你实际上没有做任何事情。 你是说左边的排序 上半年，排序的右半​​部分， 但你不能告诉 我怎么你这样做。 

但要记住，只要 阵列是一个单一元件， 我们可以宣布它排序。 然后，我们就可以将它们组合在一起。 而这实际上是 背后归并排序基本思想， 是要打破它，这样 你的数组的大小之一。 然后你从那里重建家园。 

合并排序是肯定 一个复杂的算法。 而且它也是一个小 复杂的可视化。 所以希望，可视化，我 这里将帮助你跟着。 我会尽我所能叙述的事情 并继续通过这个多一点 慢慢比其他的 只是希望得到你的头 各地背后归并排序的思想。 

因此，我们有相同的阵列作为 其他排序算法视频 如果你看过them-- 六元素的数组。 在这里，我们的伪代码排序 左半，排序右半 合并的两半一起。 因此，让我们利用这个非常暗砖红色 数组和排序它的左半边。 

所以暂且，我们将 忽略右边的东西。 它的存在，但我们 不是在这一步呢。 我们不是在排序 阵列的右半。 我们在左边的排序 一半的阵列。 而贪图 被多一点 清晰的，这样我就可以参考 到了哪一步，我们是上， 我要去切换 颜色这套橙色的。 现在，我们还在谈论 原来阵列相同的左一半。 但我希望，通过能够 指各种物品的颜色， 它会让它多了几分 不清楚什么是怎么回事。 

好了，现在我们有一个 三元数组。 我们怎么样的这个左半 阵列，这仍然是这个步骤？ 我们试图向左排序 一半的砖红色array--的 其中左一半 我现在已经橙色。 

好了，我们可以尝试 再次重复这个过程。 因此，我们仍然在 试图梳理中间 完整阵列的左半部。 的左半 阵列，我只是去 任意决定的左半 将比右半较小， 因为这恰巧 包括三个部分。 

所以我会说， 左半阵列的左半 只是五行说。 五，作为一个单一的元素 阵列，我们知道如何排序。 所以五是排序。 我们只是要声明。 这是一个单元素数组。 

所以，我们现在已经排序 左half--的左半 或者更确切地说，我们已经排序 橙色的左半部。 所以，现在，为了仍然完整 整个阵列的左半边， 我们需要的右半排序 的橙色或这个东西。 我们该怎么做呢？ 好了，我们有两个元素的数组。 因此，我们可以排序的左半 阵列，这是两个。 两个是单一元件。 因此，它的排序默认情况下。 然后，我们可以排序的右半 该部分阵列，所述一个的。 这类型的默认。 

现在这是第一次 我们已经达成了合并的步骤。 我们已经完成了，虽然 那种我们现在嵌套down-- 这就是那种棘手的 递归的是， 你需要保持你的 脑袋一下我们在哪里。 因此，我们在左边的已排序 一半的橙色部分。 

而现在，我们在整理的中间 橙色部的右半部分。 而在这过程中，我们 现在即将要上台阶， 合并的两半一起。 当我们在看的两半 阵列的，我们看到两个和一个。 该元件是小？ 一。 

那么哪一个元素是小？ 嗯，这是两个或没有。 因此，这两种。 所以，现在，想再次回到框架 我们所处的背景下， 我们已经整理了 橙色的左半 和原点的右半部。 我知道我已经改变了颜色 再次，但是这就是我们。 而我之所以这样做 是因为这个过程是 要继续下去，迭代下降。 我们已经排序的左 半前橙色 和前橙色的右半部分。 

现在，我们需要合并这些 两半了。 这是我们的第一步。 所以我们考虑所有的 元素是现在绿， 原数组的左半部。 我们合并这些 使用相同的过程 我们为合并两个 和一个刚才。 

左半，最小 左边一半元件是五。 上的最小元素 右半边是其中之一。 其中哪些是小？ 一。 

上的最小元素 左半边是五。 上的最小元素 右半边为两个。 什么是最小的？ 二。 然后最后五 什么都没有，可以说五位。 

好了，这么大的画面，让我们 休息一秒钟 并找出我们在哪里。 如果我们从开始 一开始，我们 现在已经完成了 整体阵列只 的伪代码一步在这里。 我们已经整理了 阵列的左半部。 

回想一下，原 为了五岁，二，一。 通过经历这个过程 和筑巢下来，重复， 继续打破问题 分解成更小和更小的部分， 现在我们已经完成 步骤的伪代码之一 对于整个起动阵列。 我们已经整理了左前卫。 

所以，现在，让我们定格在那里。 现在，让我们来排序的权利 原来的一半数组。 而我们要做到这一点 经历同样的迭代 打破下来的过程 然后将它们合并在一起。 

这样的左半 红色，或左半 原稿的右半部 阵，我会说是三。 再次，我是一致的在这里。 如果你有一个奇怪的 元件的数目，它 并没有真正也罢 你让左边的一个小 或者是正确的要小。 

重要的是，只要你 遇到在进行这个问题 合并，就需要保持一致。 要么你总是需要 使一个左侧小 或总是需要使 右侧小。 在这里，我选择永远 使左侧小 当我的数组，还是我的 子阵列，是一个奇怪的大小。 

三是单一元件， 所以它的排序。 我们充分利用这一假设 我们整个过程为止。 所以，现在让我们来排序的权利 一半的右边一半的， 或红色的右半边。 

同样，我们需要拆分下来。 这不是一个单一的元件阵列。 我们不能宣布它排序。 所以首先，我们要 在左半排序。 

左半是单一元件， 所以它的排序默认情况下。 然后，我们要排序的权利 一半，这是单一元件。 它的排序默认情况下。现在， 我们可以合并这两个在一起。 四个较小，并 然后6越小。 

此外，我们还有什么在这一点上做了什么？ 我们已经排序的左 一半的右边一半。 或回到原来的 这是有颜色的， 我们已经排序的左 一半的较软的红色。 它最初是一个黑砖 红现在是一个更柔和的红色， 或者，这是一个较软的红色。 

然后我们排序 的较软红右半边。 现在的，很好，他们是绿色还是一样，只 因为我们正在经历一个过程。 我们要重复 这一遍又一遍。 

所以，现在，我们可以合并这些 两半。 这就是我们在这里做。 所以黑线刚 划分左半 与这种部分的右半部分。 

我们比较的最小值 在array--左侧 还是原谅了我，最小 左半的值 到的右侧的值最小 一半，并找到三个较小。 而现在有点优化的，对不对？ 有其实也没什么 留在左侧。 

没有什么剩余 在左侧， 所以我们可以有效地 只是move--我们可以声明 它的其余部分实际上是 排序，只是它钉住 对，因为没有什么 别人进行比较的。 我们知道，右侧 右侧是排序。 

好了，现在让我们再次冻结和 找出我们所处的故事。 在整个阵列， 我们有什么成就？ 我们实际上已经完成 现在步骤一和步骤二。 我们的排序左半，和 我们整理了右半边。 

所以，现在，这一切仍然是我们 这些两半合并在一起。 所以我们比较具有最低值 阵列的每个一半的元件 反过来，然后继续。 一个是小于3，所以一去。 

二是不到三年，所以二除。 三是小于5，所以三去。 四是小于5，因此四去。 然后，五是不到六个月， 六是所有仍然存在。 

现在，我知道，这是一个很大的步骤。 而且我们留下了很多 记忆在我们唤醒。 而这正是那些灰色方格。 它可能感觉就像是拿了 很多的时间比插入排序，气泡 排序或选择排序。 

但实际上，由于 很多这些过程 都发生在同一时间 -  这是一件好事，我们将再次 谈论当我们谈论 递归在未来video-- 这种算法实际上 显然是根本 比什么不同 我们已经看到前 但是也显著 更有效。 

这是为什么？ 那么，在最坏的 的情况下，我们有 分裂n个元素了 然后重新组合它们。 但是，当我们重新组合 他们，我们在做什么 基本上是翻倍 较小的数组的大小。 我们有一大堆的一个元素 阵列我们有效 合并成2个元素的数组。 然后我们把这些 二元阵列 并结合在一起成 4元件阵列，等等， 等等，依此类推，直到我们 有一个单个n元件阵列。 

但究竟有多少倍增 它才能让到n？ 回想一下电话簿的例子。 多少次，我们要撕 电话薄了一半，要多 次我们是否撕电话簿 在一半中，如果电话簿的大小 翻倍？ 这里只有一个，对不对？ 

因此，有某种 这里对数的元素。 但是，我们也还是要至少 看看所有的n个元素。 因此，在最坏的情况下， 合并排序运行时间为n日志ñ。 我们来看看 所有的n个元素， 我们必须把它们混合起来 一起在记录n个步骤。 在最好的情况下， 该阵列是完全排序。 那很棒。 但基于算法，​​我们这里有， 我们还是要分裂和重组。 虽然在这种情况下， 再结合是一种无效的。 它是不需要的。 但是，我们仍然要经过 整个过程呢。 

因此，在最好的情况下 而在最坏的情况下， 该算法运行在的n log n次。 合并排序肯定是有点棘手 比其他主排序算法 我们谈到CS50但 实质上更加强大。 

所以，如果你发现 有时需要它 或用它来排序 大型数据集，得到 你的头左右递归的想法 将是真正强大。 而这将让你的 节目真的更有效 使用分类合并与其他任何东西。 我是道格·劳埃德。 这是CS50。