1.6「Stanford Algorithms」Merge So

Okay.

So in this video, we'll get our first sense of what it's actually like to analyze an algorithm.

And we'll do that by first of all reviewing a famous sorting algorithm, namely the Merge Sort algorithm.

And then giving a really fairly mathematically precise upper bound on exactly how many operations the Merge Sort algorithm requires to correctly sort an input array.

So I feel like I should begin with a bit of an apology.

Here we are in 2012, a very futuristic sounding date.

And yet I'm beginning with a really quite ancient algorithm.

So for example, Merge Sort was certainly known, to John Von Neumann all the way back in 1945.

So, what justification do I have for beginning, you know, a modern class in algorithms with such an old example? Well, there's a bunch of reasons.

One, I haven't even put down on the slide, which is like a number of the algorithms we'll see, "Merge Sort" as an oldie but a goodie.

So it's over 60, or maybe even 70 years old.

But it's still used all the time in practice, because this really is one of the methods of choice for sorting.

The standard sorting algorithm in the number of programming libraries.

So that's the first reason.

But there's a number of others as well that I want to be explicit about.

So first of all, throughout these online courses, we'll see a number of general algorithm design paradigms ways of solving problems that cut across different application domains.

And the first one we're going to focus on is called the Divide-and-Conquer algorithm design paradigm.

So in Divide-and-Conquer, the idea is, you take a problem, and break it down into smaller sub problems which you then solve recursively, ......

and then you somehow combine the results of the smaller sub-problem to get a solution to the original problem that you actually care about.

And Merge Sort is still today's the, perhaps the, most transparent application of the Divide-and-Conquer paradigm, ......

that will exhibit very clear what the paradigm is, what analysis and challenge it presents, and what kind of benefits you might derive.

As for its benefits, so for example, you're probably all aware of the sorting problem.

Probably you know some number of sorting algorithms perhaps including Merge Sort itself.

And Merge Sort is better than a lot of this sort of simpler, I would say obvious, sorting algorithms, ......

so for example, three other sorting algorithms that you may know about, but that I'm not going to discuss here.

If you don't know them, I encourage you to look them up in a text book or look them up on the web.

Let's start with three sorting algorithms which are perhaps simpler, first of all is "Selection Sort".

So this is where you do a number of passes through the way repeatedly, identifying the minimum of the elements that you haven't looked at yet, ......

so you're basically a linear number of passes each time doing a minimum computation.

There's "Insertion Sort", which is still useful in certain cases in practice as we will discuss, but again it's generally not as good as Merge Sort, ......

where you will repeatedly maintain the invariant that prefix view of array, which is sorted version of those elements.

So after ten loops of Insertion Sort, you'll have the invariant that whatever the first ten elements of the array are going to be in sorted order, ......

and then when Insertion Sort completes, you'll have an entire sorted array.

Finally, some of you may know about "Bubble Sort", which is where you identify adjacent pairs of elements which are out of order, ...

and then you do repeated swaps until in the end the array is completely sorted.

Again I just say this to jog your memory, these are simpler sorts than Merge Sort, ......

but all of them are worse in the sense that they're lack in performance in general, which scales with N^2, ......

and the input array has N elements, so they all have, in some sense, quadratic running time.

But if we use this non-trivial Divide-and-Conquer approach, or non-obvious approach, we'll get a, as we'll see, a much better running time than this quadratic dependence on the input.

Okay? So we'll get a win, first sorting in Divide-and-Conquer, and Merge Sort is the algorithm that realizes that benefit.

So the second reason that I wanna start out by talking about the Merge Sort algorithm, is to help you calibrate your preparation.

I think the discussion we're about to have will give you a good signal for whether you're background's at about the right level, of the audience that I'm thinking about for this course.

So in particular, when I describe the Merge Sort algorithm, you'll notice that I'm not going to describe in a level of detail that you can just translate it line by line into a working program in some programming language.

My assumption again is that you're a sort of the programmer, and you can take the high-level idea of the algorithm, how it works, ......

and you're perfectly capable of turning that into a working program in whatever language you see fit.

So hopefully, I don't know, it may not be easy the analysis of Merge Sort discussion.

But I hope that you find it at least relatively straight forward, ....

because as the course moves on, we're going to be discussing algorithms and analysis which are a bit more complicated than the one we're about to do with Merge Sort.

So in other words, I think that this would be a good warm-up for what's to come.

Now another reason I want to discuss Merge Sort is that our analysis of it will naturally segment discussion of how we analyze the algorithms in this course and in general.

So we're going to expose a couple of assumptions in our analysis, we're focus on worst case behavior, ......

or we'll look for guarantees on performance on running time that hold for every possible input on a given size, ...

and then we'll also expose our focus on so called "Asymptotic Analysis", which meaning will be much more concerned with the rate of growth on an algorithms performance than on things like low-order terms or on small changes in the constant factors.

Finally, we'll do the analysis of Merge Sort using what's called as "Recursion-Tree" method.

So this is a way of tying up the total number of operations that are executed by an algorithm.

And as we'll see a little bit later, this Recursion-Tree method generalizes greatly.

And it will allow us to analyze lots of different recursive algorithms, lots of different Divide-and-Conquer algorithms, including the integer multiplication algorithm that we discussed in an earlier segment.

So those are the reasons to start out with Merge Sort.

So what is the computational problem that Merge Sort is meant to solve? Well, presumably, you all know about the sorting problem.

But let me tell you a little bit about it anyways, just so that we're all on the same page.

So, we're given as input.

An array of N numbers in arbitrary order, and the goal of course is to produce output array where the numbers are in sorted order, let's say, from smallest to largest.

Okay so, for example, we could consider the following input array, and then the goal would be to produce the following output array.

Now one quick comment.

You'll notice that here in input array, it had eight elements, all of them were distinct, it was the different integers, between 1 and 8.

Now the sorting problem really isn't any harder if you have duplicates, in fact it can even be easier, ......

but to keep the discussion as simple as possible let's just, among friends, go ahead and assume that they're distinct, for the purpose of this lecture.

And I'll leave it as an exercise which I encourage you to do, which is to think about how the Merge Sort algorithm implementation and analysis would be different, if at all, if there were ties, okay? Go ahead and make the distinct assumption for simplicity from here on out.

Okay, so before I write down any pseudo code for Merge Sort, let me just show you how the algorithm works using a picture, ......

and I think it'll be pretty clear what the code would be, even just given a single example.

So let's go ahead and consider the same unsorted input array that we had on the previous slide.

So the Merge Sort algorithm is a recursive algorithm, and again, that means that a program which calls itself and it calls itself on smaller sub problems of the same form, okay? So the Merge Sort is its purpose in life is to sort the given input array.

So it's going to spawn, or call itself on smaller arrays.

And this is gonna be a canonical Divide-and-Conquer application, where we simply take the input array, we split it in half, we solve the left half recursively, we solve the right half recursively, and then we combine the results.

So let's look at that in the picture.

So the first recursive call gets the first four elements, the left half of the array, namely 5, 4, 1, 8.

And, of course, the other recursive call is gonna get the rest of the elements, 7, 2, 6, 3.

You can imagine these has been copied into new arrays before they're given to the recursive calls.

Now, by the magic of recursion, or by induction if you like, the recursive calls will do their task.

They will correctly sort each of these arrays of four elements, and we'll get back sorted versions of them.

So from our first recursive call, we receive the output, 1, 4, 5, 8, and from the second recursive call, we received the sorted output, 2, 3, 6, 7.

So now, all the remains to complete the Merge Sort is to take the two results of our recursive calls, these two sorted elements of length-4, and combine them to produce the final output, namely the sorted array of all eight of the input numbers.

And this is the step which is called "Merge".

And hopefully you are already are thinking about how you might actually implement this merge in a computationally efficient way.

But I do owe you some more details.

And I will tell you exactly how the merge is done.

In effect, you just walk pointers down each of the two sort of sub-arrays, copying over, populating the output array in the sorted order.

But I will give you some more details in just a slide or two.

So that's Merge Sort in a picture.

Split it in half, solve recursively, and then have some slick merging procedure to combine the two results into a sorted output.

好的。

因此，在此视频中，我们将对分析算法的实际感受有一个第一感觉。

首先，我们将回顾一种著名的排序算法，即合并排序算法。

然后为合并排序算法准确地对输入数组进行正确排序所需的操作数提供了一个数学上相当精确的上限。

所以我觉得我应该从道歉开始。

我们在2012年到来，这是一个非常具有未来派意义的约会。

但是我从一个非常古老的算法开始。

因此，例如，合并排序（Merge Sort）早在1945年就一直被约翰·冯·诺伊曼（John Von Neumann）所熟知。

那么，我知道以这样一个古老的例子开始一门现代的算法类有什么道理？好吧，有很多原因。

一个，我什至还没有放下幻灯片，就像我们将看到的许多算法一样，“合并排序”既是老歌，又是好东西。

因此，它已经有60多年，甚至有70年的历史。

但这实际上一直在使用，因为这确实是排序的一种选择方法。

多个编程库中的标准排序算法。

这是第一个原因。

但是我也想明确指出其他一些内容。

因此，首先，在这些在线课程中，我们将看到许多通用的算法设计范式来解决跨越不同应用程序领域的问题。

我们首先要关注的是分而治之算法设计范例。

因此，在“分而治之”中，想法是，您将一个问题分解为较小的子问题，然后递归解决......

然后以某种方式组合较小的子问题的结果，以解决您实际关心的原始问题。

而且，Merge Sort仍然是分而治之范式的当今，也许是最透明的应用程序，......

这将非常清楚地表明该范式是什么，它所呈现的分析和挑战以及您可能获得的好处。

至于它的好处，例如，您可能都知道排序问题。

也许您知道一些排序算法，包括Merge Sort本身。

而且，Merge Sort比许多这种简单的方法要好，我想说很明显的是，排序算法，......

因此，举例来说，您可能会知道其他三种排序算法，但在此不做讨论。

如果您不认识它们，建议您在教科书中查找它们或在网上查找它们。

让我们从三种可能更简单的排序算法开始，首先是“选择排序”。

因此，在这里您将反复进行多次遍历，找出您尚未看过的最少元素，......

因此，每次进行最少的计算时，您的遍历基本上都是线性的。

这里有“插入排序”，在实践中，正如我们将要讨论的那样，它在某些情况下仍然有用，但是通常它不如合并排序好......

您将在其中重复维护数组的不变前缀视图，即这些元素的排序版本。

因此，在经过十次插入排序循环之后，您将具有不变性，即数组的前十个元素将按排序顺序进行......

然后，当“插入排序”完成时，您将拥有一个完整的排序数组。

最后，你们中的某些人可能知道“气泡排序”，即在其中识别乱序的相邻元素对，...

然后重复进行交换，直到最后对数组进行完全排序。

我再次说这是为了唤起您的记忆，这些排序比合并排序更简单，......

但是从总体上来说，它们都缺乏性能，这在所有方面都更糟，其性能随着N ^ 2，......

并且输入数组具有N个元素，因此在某种意义上它们都具有二次运行时间。

但是，如果我们使用这种非平凡的分而治之方法或非显而易见的方法，我们将看到，与这种对输入的二次依赖相比，运行时间要好得多。

好的？因此，我们将获得胜利，首先使用分而治之进行排序，而合并排序就是实现这一优势的算法。

因此，我想开始谈论“合并排序”算法的第二个原因是帮助您校准准备工作。

我认为我们将要进行的讨论将为您提供一个很好的信号，表明您是否对本课程正在考虑的受众群体的背景知识处于适当的水平。

因此，尤其是当我描述“合并排序”算法时，您会注意到，我不会详细描述可以将其逐行转换为某种编程语言的工作程序。

我的假设再次是您是一种程序员，您可以对算法进行高级了解，了解其工作原理，......

并且您完全有能力以您认为合适的语言将其转换为工作程序。

因此，希望我不知道，对“合并排序”讨论进行分析可能并不容易。

但我希望您至少发现它比较直接。

因为随着课程的进行，我们将讨论算法和分析，这些算法和分析比我们将要使用“合并排序”的算法和分析要复杂一些。

换句话说，我认为这将是对即将发生的事情的良好热身。

现在，我要讨论合并排序的另一个原因是，我们对其进行的分析将自然而然地分割了关于如何在本课程以及一般情况下分析算法的讨论。

因此，我们将在分析中暴露一些假设，我们将重点放在最坏情况下的行为上，......

否则，我们将寻求对运行时性能的保证，这些保证对于给定大小的每个可能的输入都适用，...

然后，我们还将重点介绍所谓的“渐近分析”，这意味着与算法性能的增长速度相比，与低阶项或常数因子的小幅变化相比，它的关注程度更高。

最后，我们将使用所谓的“递归树”方法对合并排序进行分析。

因此，这是一种限制算法执行的操作总数的方法。

稍后我们将看到，此递归树方法具有很大的概括性。

这将使我们能够分析许多不同的递归算法，许多不同的分而治之算法，包括我们在前面的部分中讨论的整数乘法算法。

因此，这些就是开始使用“合并排序”的原因。

那么，合并排序要解决的计算问题是什么？好吧，大概大家都知道排序问题。

但是，无论如何，我还是要告诉您一点，以便我们都在同一页面上。

因此，我们得到了输入。

N个以任意顺序排列的数字的数组，当然，目标是产生输出数组，其中的数字按从小到大的顺序排列。

好的，例如，我们可以考虑以下输入数组，然后目标是生成以下输出数组。

现在快速评论一下。

您会注意到，在输入数组中，它有八个元素，所有元素都是不同的，是1到8之间的不同整数。

现在，如果您有重复项，则排序问题实际上并没有变得更加困难，实际上，它甚至更容易实现，......

但是为了使讨论尽可能简单，让我们在朋友中继续前进，并假设他们与众不同，就本讲座而言。

我会鼓励您去做一个练习，它是在考虑合并排序算法的实现和分析（如果有的话，如果有联系的话）会有什么不同，好吗？从现在开始，对简单性做出独特的假设。

好吧，所以在为合并排序写下任何伪代码之前，让我向您展示算法如何使用图片工作，......

我认为即使只是给出一个示例，代码也将是清楚的。

因此，让我们继续考虑与上一张幻灯片相同的未排序输入数组。

因此，合并排序算法是一种递归算法，同样，这意味着一个程序会自行调用，并且会在具有相同形式的较小子问题上自行调用，好吗？因此，合并排序的主要目的是对给定的输入数组进行排序。

因此它将产生，或在较小的数组上调用自身。

这将是一个规范的分而治之应用程序，我们只需要简单地将输入数组作为输入数组，我们将其分成两半，我们递归求解左半边，我们递归求解右半边，然后将结果组合起来。

因此，让我们在图片中看一下。

因此，第一个递归调用将获取前四个元素，即数组的左半部分，即5、4、1、8。

当然，另一个递归调用将获得其余元素7、2、6、3。

您可以想象将它们复制到新数组中，然后再进行递归调用。

现在，通过递归的魔力，或者通过归纳法（如果您愿意），递归调用将完成其任务。

他们将正确地对四个元素的每个数组进行排序，然后我们将返回它们的排序版本。

因此，从第一个递归调用中，我们收到输出1、4、5、8，从第二个递归调用中，我们收到排序后的输出2、3、6、7。

因此，现在，完成合并排序的所有剩余内容都是采用递归调用的两个结果（长度为4的这两个排序元素），并将它们组合以产生最终输出，即所有八个输入的排序数组数字。

这就是所谓的“合并”步骤。

希望您已经在考虑如何以计算有效的方式实际实现此合并。

但是我欠您一些细节。

我会告诉您确切的合并方法。

实际上，您只需将指针沿两种子数组中的每一种向下走，进行复制，然后按排序顺序填充输出数组。

但是，我将在一两张幻灯片中为您提供更多详细信息。

这就是合并排序图片。

将其分成两部分，递归求解，然后执行一些巧妙的合并过程，将两个结果合并为一个排序的输出。