[Musikwiedergabe] 

DOUG LLOYD: OK, so dass eine Zusammenführung Art ist ein weiterer Algorithmus dass wir verwenden können, zu sortieren, die Elemente eines Arrays. Aber wie wir sehen werden, es hat eine sehr grundlegende Unterschied von Selection Sort, bubble sortieren und Insertion Sort dass es wirklich ziemlich clever. 

Die Grundidee hinter merge Art ist es, kleineren Arrays sortieren und dann diese Arrays zu verbinden zusammen oder verschmelzen them-- daher der name-- in sortierter Reihenfolge. Die Art und Weise, die Art tut verschmelzen Dies ist durch den Einsatz eines Werkzeugs aufgerufen Rekursion, was was ist werden wir werden reden bald, aber wir haben nicht wirklich über noch gesprochen. 

Hier ist die Grundidee hinter merge sort. Sortieren Sie die linke Hälfte des Feldes, vorausgesetzt, n größer als 1 ist. Und was ich meine, wenn ich sage, vorausgesetzt, n größer als 1 ist, Ich denke, dass wir uns einig, dass, wenn ein Array besteht nur aus einem einzigen Element, es ist sortiert. Wir wissen nicht wirklich brauchen , etwas zu tun. Wir können einfach erklären sie sortiert werden. Es ist nur ein einziges Element. 

So ist die Pseudocode, ist wieder sortieren Sie die linke Hälfte des Feldes, dann sortieren die rechte Hälfte das Array, dann verschmelzen die beiden Hälften zusammen. Jetzt schon werden Sie vielleicht denken, es ist irgendwie gerade klingt wie Sie setzen off the-- du nicht wirklich etwas zu tun. Du sagst, sortieren Sie die linke Hälfte, sortieren Sie die rechte Hälfte, aber du bist nicht sagen mir, wie du es tust. 

Aber denken Sie daran, dass, solange ein Array ein einzelnes Element ist, können wir erklären, es sortiert. Dann können wir nur kombinieren sie zusammen. Und das ist eigentlich das Grundgedanke merge sort, ist, es zu brechen, so dass Ihre Arrays der Größe eins. Und dann von dort wieder aufzubauen. 

Merge sort ist auf jeden Fall ein komplizierter Algorithmus. Und es ist auch ein wenig kompliziert zu visualisieren. Also hoffentlich, die Visualisierung, die ich habe hier wird Ihnen helfen, zusammen zu folgen. Und ich werde mein Bestes versuchen, um die Dinge zu erzählen und durch diese ein wenig mehr gehen langsamer als die anderen, nur um hoffentlich den Kopf um die Ideen hinter merge sort. 

So haben wir das gleiche Array wie der andere Sortieralgorithmus Videos Wenn Sie gesehen haben them-- ein Sechs-Element-Array. Und unsere Pseudocode ist hier sort die linke Hälfte, sortieren Sie die rechte Hälfte, verschmelzen die beiden Hälften zusammen. Werfen wir also diese sehr dunklen Ziegelrot Array und sortieren Sie die linke Hälfte. 

Also vorerst werden wir das Zeug auf der rechten Seite zu ignorieren. Es ist da, aber wir sind nicht bei diesem Schritt vor. Wir sind nicht in der Art, rechte Hälfte des Arrays. Wir sind im Art die linke Hälfte des Feldes. Und nur um von einer etwas schwie klar, so verweise ich kann in welchem ​​Schritt sind wir auf, Ich werde den Schalter Farbe dieser Satz bis orange. Jetzt werden wir noch über die Gespräche elbe linke Hälfte des ursprünglichen Arrays. Aber ich hoffe, dass durch die Möglichkeit, beziehen sich auf die Farben der verschiedenen Elemente, es wird es ein wenig mehr zu machen klar, was hier vor sich geht. 

OK, so jetzt haben wir ein drei Elementanordnung. Wie können wir sortieren die linke Hälfte davon Anordnung, die immer noch diese Stufe? Wir versuchen, die linke sortieren Hälfte des Ziegelrot array-- die linke Hälfte von denen Ich habe jetzt orange gefärbt. 

Nun, wir könnten versuchen, und Wiederholen Sie diesen Vorgang noch einmal. So sind wir immer noch in der Mitte versucht zu sortieren die linke Hälfte des vollen Array. Die linke Hälfte des Array, Ich werde einfach willkürlich entscheiden, dass die linke Hälfte wird kleiner als die rechte Hälfte, denn dies geschieht, bestehen aus drei Elementen. 

Und so werde ich sagen, dass die linke Hälfte der linken Hälfte der Array- ist nur das Element fünf. Five, ein einzelnes Element Array, wir wissen, wie es zu sortieren. Und so fünf sortiert ist. Wir sind gerade dabei, das zu erklären. Es ist ein Einzelelement-Array. 

Also haben wir jetzt nach der linke Hälfte des linken half-- oder besser gesagt, wir sortiert haben die linke Hälfte der Orange. So, jetzt, um noch vollständig linke Hälfte der Gesamt Arrays, wir brauchen, um die rechte Hälfte zu sortieren der orange, oder diesem Zeug. Wie wir das machen? Nun, wir haben eine Zwei-Element-Array. So können wir die linke Hälfte sortieren des Arrays, die zwei ist. Zwei ist ein einzelnes Element. So ist es standardmäßig sortiert. Dann können wir die rechte Hälfte zu sortieren des Teils des Arrays, der einen. Das ist eine Art standardmäßig. 

Dies ist nun zum ersten Mal haben wir eine Zusammenführungsschritt erreicht. Wir haben abgeschlossen, obwohl wir jetzt Art verschachtelt down-- und das ist die Art von tricky Sache mit Rekursion, Sie Ihre halten müssen Kopf darüber, wo wir sind. Deshalb haben wir uns irgendwie links die Hälfte der orangen Teil. 

Und jetzt, die in der Mitte des Sortier sind die rechte Hälfte der orangen Teil. Und in diesem Verfahren werden wir nun zu den auf dem Schritt, verschmelzen die beiden Hälften zusammen. Wenn wir uns den beiden Hälften des Arrays, sehen wir zwei und eins. Welches Element ist kleiner? Ein. 

Dann welches Element kleiner ist? Nun, es ist zwei oder nichts. So ist es zwei. So, jetzt, nur um wieder umrahmen wo wir in Zusammenhang stehen, wir sortiert haben die linke Hälfte der Orange und die rechte Hälfte des Ursprungs. Ich weiß, ich habe die Farbe verändert wieder, aber das ist, wo wir waren. Und der Grund, warum ich tat dies, Denn dieses Verfahren werde weitermachen, Iteration nach unten. Wir haben die linken sortiert die Hälfte der ehemaligen Orangen und die rechte Hälfte des ehemaligen Orange. 

Jetzt müssen wir diejenigen, verschmelzen zwei Hälften zu zusammen. Das ist der Schritt, den wir unterwegs sind. So dass wir alle das betrachten Elemente, die nun grün sind, die linke Hälfte des ursprünglichen Arrays. Und wir zusammenführen denen Verwendung des gleichen Verfahrens wir für das Zusammenführen zweier tat und vor einem nur einen Augenblick. 

Die linke Hälfte, die kleinste Element auf der linken Hälfte ist fünf. Das kleinste Element die rechte Hälfte gehört. Welche dieser kleiner ist? Ein. 

Das kleinste Element die linke Hälfte ist fünf. Das kleinste Element die rechte Hälfte ist zwei. Was ist der kleinste? Zwei. Und dann schließlich fünf nichts, können wir sagen, fünf. 

OK, so dass große Bild, lassen Sie uns machen Sie eine Pause für eine Sekunde und herausfinden, wo wir sind. Wenn wir aus gestartet Anbeginn wir haben jetzt abgeschlossen die Gesamtanordnung nur einen Schritt des Pseudocode. Wir haben nach der linken Hälfte des Arrays. 

Daran erinnern, dass der Original Um fünf war, zwei, eins. Indem wir durch diesen Prozess und nisten nach unten und wiederholen, Weiterbildung, um das Problem zu brechen sich in immer kleinere Teile, Wir haben jetzt Schritt eine der Pseudocode für die gesamte Ausgangs Array. Wir haben seine linke Hälfte sortiert. 

So, jetzt wollen wir es einfrieren. Und jetzt ist irgendwie das Recht lassen die Hälfte des ursprünglichen Arrays. Und wir werden, dass durch zu tun gehen durch die gleiche iterative Prozess der Unterbrechung Dinge nach unten und dann zusammen Zusammenlegung. 

So ist die linke Hälfte des rot, oder die linke Hälfte der rechten Hälfte des ursprünglichen Array, werde ich sagen, ist drei. Auch hier bin ich, hier konsequent. Wenn Sie eine ungerade haben Anzahl der Elemente, so spielt eigentlich keine Rolle, ob Sie links ein kleiner machen oder die richtige kleiner. 

Was zählt, ist, dass, wann immer Sie begegnen diesem Problem bei der Durchführung eine Zusammenführung, Sie müssen konsequent sein. Entweder müssen immer Sie links Seite kleiner oder immer brauchen, um die rechte Seite kleiner. Hier habe ich immer gewählt haben machen die linke Seite kleiner wenn meine Array oder meine Sub-Array ist aus einer ungeraden Größe. 

Drei ein einzelnes Element ist, und so sortiert wird. Wir haben diese Annahme Leveraged in unserer gesamten Prozess so weit. So, jetzt ist irgendwie das Recht lassen Hälfte der rechten Hälfte, oder die rechte Hälfte des roten. 

Auch hier müssen wir diese gespalten. Dies ist nicht ein einzelnes Element-Array. Wir können uns nicht erklären, es sortiert. Und so zuerst, wir gehen um die linke Hälfte zu sortieren. 

Die linke Hälfte ist ein einzelnes Element, also ist es Art von standardmäßig. Dann werden wir das Recht zu sortieren Hälfte, die ein einzelnes Element ist. Es ist standardmäßig sortiert. Und jetzt, Wir können diese beiden miteinander verschmelzen. Vier kleiner ist, und dann sechs ist kleiner. 

Wieder was haben wir an dieser Stelle getan? Wir haben die linken sortiert die Hälfte der in der rechten Hälfte. Oder gehen zurück auf die ursprüngliche Farben, die dort waren, wir haben die linken sortiert Hälfte des weicheren rot. Es war ursprünglich ein dunklem Backstein rot und jetzt ist es eine weichere rot, oder es war ein weicher rot. 

Und dann haben wir sortiert haben die rechte Hälfte des weicheren rot. Nun gut, sie sind wieder grün, nur weil wir durch einen Prozess gehen. Und wir haben zu wiederholen, das immer und immer. 

So, jetzt können wir diese zusammenführen zwei Hälften zusammen. Und das ist, was wir hier tun. Also die schwarze Linie nur unterteilt die linke Hälfte und die rechte Hälfte dieser Art teil. 

Wir vergleichen den kleinsten Wert auf der linken Seite des array-- oder entschuldigen Sie mich, den kleinsten Wert der linken Hälfte auf den kleinsten Wert der rechten Halb und feststellen, dass drei kleiner ist. Und jetzt ein bisschen wie eine Optimierung, nicht wahr? Es gibt eigentlich nichts nach links auf der linken Seite. 

Es gibt noch nichts auf der linken Seite, so können wir effizient nur move-- können wir erklären, der Rest ist eigentlich sortiert und nur heften auf, denn es gibt nichts, sonst gegen zu vergleichen. Und wir wissen, dass die rechte Seite von der rechten Seite sortiert wird. 

OK, so jetzt ist wieder einfrieren lassen und herauszufinden, wo wir in der Geschichte sind. In der Gesamtanordnung, Was haben wir erreicht? Wir haben tatsächlich zu erreichen Jetzt die Schritte eins und Schritt zwei. Wir sortiert die linke Hälfte, und wir nach die rechte Hälfte. 

So, jetzt ist für uns alles, was bleibt um diese beiden Hälften miteinander verschmelzen. So dass wir vergleichen die niedrigsten bewertet Element jeder Hälfte der Anordnung der Reihe nach und gehen. Eine weniger als drei ist, so geht man. 

Zwei weniger als drei beträgt, so dass zwei hinausgeht. Drei weniger als 5, so dass drei geht. Vier kleiner ist als 5, so vier geht. Dann fünf kleiner als sechs, und sechs ist alles, was bleibt. 

Nun, ich weiß, das war eine Menge von Schritten. Und wir haben eine Menge links Speicher in unserem Kielwasser. Und das ist, was die grauen Quadrate sind. Und es ist wahrscheinlich das Gefühl, dass fand ein viel länger als Insertion Sort, bubble sortieren oder Auswahl sort. 

Aber eigentlich, denn ein Viele dieser Prozesse werden gleichzeitig Zeit-- geschieht die etwas, das wir ist, wieder, reden, wenn wir sprechen Rekursion in einer zukünftigen video-- dieser Algorithmus tatsächlich klar ist grundsätzlich anders als alles, wir zuvor gesehen haben sondern auch wesentlich effizienter. 

Warum ist das so? Nun, im schlimmsten Case-Szenario, haben wir um n Elemente aufzuteilen und dann rekombinieren sie. Aber wenn wir rekombinieren ihnen, was wir tun, ist im Grunde eine Verdoppelung der Größe der kleineren Arrays. Wir haben eine Reihe von einem Element Arrays, die wir effektiv kombiniert in zwei Elementanordnungen. Und dann nehmen wir diejenigen, zwei Elementanordnungen und miteinander kombinieren sie zu Vierelement-Arrays, und so weiter, und so weiter, und so weiter, bis wir eine einzige n Elementanordnung. 

Aber wie viele Dopplungen dauert es, bis zu n zu bekommen? Denken Sie zurück an das Telefonbuch Beispiel. Wie oft müssen wir zu zerreißen haben das Telefonbuch in der Hälfte, wie viele Mal wollen wir das Telefonbuch zerreißen haben in der Hälfte, wenn die Größe des Telefonbuchs verdoppelt? Es gibt nur ein, nicht wahr? 

Es gibt also eine Art von logarithmische Element. Wir haben aber auch noch zumindest Blick auf alle der n Elemente. Also im ungünstigsten Fall Mergesort läuft in n log n. Wir haben, zu betrachten alle der n Elemente, und wir, sie zu kombinieren haben zusammen in log n Gruppen von Schritten. Im besten Fall, das Array perfekt sortiert. Das ist großartig. Aber auf dem Algorithmus haben wir hier, wir haben immer noch zu spalten und zu rekombinieren. Obwohl in diesem Fall wird das Rekombination ist eine Art unwirksam. Es ist nicht erforderlich. Aber wir haben noch durchgehen der gesamte Prozess sowieso. 

So im besten Fall und im schlimmsten Fall Dieser Algorithmus läuft in n log n Zeit. Merge sort ist auf jeden Fall ein bisschen schwieriger als die anderen Hauptsortieralgorithmen wir über CS50 gesprochen haben, ist aber wesentlich leistungsfähiger. 

Und so, wenn Sie überhaupt finden Gelegenheit, um es brauchen oder, es zu benutzen, um eine Art großen Datensatz, bekommen Ihren Kopf um die Idee der Rekursion sein wird, wirklich mächtig. Und es geht um Ihre Programme wirklich viel effizienter mit Mergesort gegen alles andere. Ich bin Doug Lloyd. Dies ist CS50.