1
00:00:00,000 --> 00:00:04,419
>> [Musikwiedergabe]

2
00:00:04,419 --> 00:00:05,401

3
00:00:05,401 --> 00:00:08,460
>> DOUG LLOYD: OK, so dass eine Zusammenführung
Art ist ein weiterer Algorithmus

4
00:00:08,460 --> 00:00:11,200
dass wir verwenden können, zu sortieren,
die Elemente eines Arrays.

5
00:00:11,200 --> 00:00:14,480
Aber wie wir sehen werden, es hat eine
sehr grundlegende Unterschied

6
00:00:14,480 --> 00:00:17,850
von Selection Sort, bubble
sortieren und Insertion Sort

7
00:00:17,850 --> 00:00:20,280
dass es wirklich ziemlich clever.

8
00:00:20,280 --> 00:00:24,290
>> Die Grundidee hinter merge
Art ist es, kleineren Arrays sortieren

9
00:00:24,290 --> 00:00:27,430
und dann diese Arrays zu verbinden
zusammen oder verschmelzen them--

10
00:00:27,430 --> 00:00:31,440
daher der name-- in sortierter Reihenfolge.

11
00:00:31,440 --> 00:00:34,230
Die Art und Weise, die Art tut verschmelzen
Dies ist durch den Einsatz eines Werkzeugs

12
00:00:34,230 --> 00:00:37,290
aufgerufen Rekursion, was was ist
werden wir werden reden bald,

13
00:00:37,290 --> 00:00:39,720
aber wir haben nicht wirklich über noch gesprochen.

14
00:00:39,720 --> 00:00:43,010
>> Hier ist die Grundidee hinter merge sort.

15
00:00:43,010 --> 00:00:46,320
Sortieren Sie die linke Hälfte des Feldes,
vorausgesetzt, n größer als 1 ist.

16
00:00:46,320 --> 00:00:49,980
Und was ich meine, wenn ich sage,
vorausgesetzt, n größer als 1 ist,

17
00:00:49,980 --> 00:00:53,970
Ich denke, dass wir uns einig, dass, wenn ein Array
besteht nur aus einem einzigen Element,

18
00:00:53,970 --> 00:00:54,680
es ist sortiert.

19
00:00:54,680 --> 00:00:56,560
Wir wissen nicht wirklich brauchen
, etwas zu tun.

20
00:00:56,560 --> 00:00:58,059
Wir können einfach erklären sie sortiert werden.

21
00:00:58,059 --> 00:01:00,110
Es ist nur ein einziges Element.

22
00:01:00,110 --> 00:01:03,610
>> So ist die Pseudocode, ist wieder
sortieren Sie die linke Hälfte des Feldes,

23
00:01:03,610 --> 00:01:08,590
dann sortieren die rechte Hälfte das Array,
dann verschmelzen die beiden Hälften zusammen.

24
00:01:08,590 --> 00:01:11,040
Jetzt schon werden Sie vielleicht
denken, es ist irgendwie gerade

25
00:01:11,040 --> 00:01:14,080
klingt wie Sie setzen off the--
du nicht wirklich etwas zu tun.

26
00:01:14,080 --> 00:01:16,330
Du sagst, sortieren Sie die linke
Hälfte, sortieren Sie die rechte Hälfte,

27
00:01:16,330 --> 00:01:19,335
aber du bist nicht sagen
mir, wie du es tust.

28
00:01:19,335 --> 00:01:22,220
>> Aber denken Sie daran, dass, solange
ein Array ein einzelnes Element ist,

29
00:01:22,220 --> 00:01:23,705
können wir erklären, es sortiert.

30
00:01:23,705 --> 00:01:25,330
Dann können wir nur kombinieren sie zusammen.

31
00:01:25,330 --> 00:01:27,788
Und das ist eigentlich das
Grundgedanke merge sort,

32
00:01:27,788 --> 00:01:31,150
ist, es zu brechen, so dass
Ihre Arrays der Größe eins.

33
00:01:31,150 --> 00:01:33,430
Und dann von dort wieder aufzubauen.

34
00:01:33,430 --> 00:01:35,910
>> Merge sort ist auf jeden Fall
ein komplizierter Algorithmus.

35
00:01:35,910 --> 00:01:38,210
Und es ist auch ein wenig
kompliziert zu visualisieren.

36
00:01:38,210 --> 00:01:41,870
Also hoffentlich, die Visualisierung, die ich
habe hier wird Ihnen helfen, zusammen zu folgen.

37
00:01:41,870 --> 00:01:45,640
Und ich werde mein Bestes versuchen, um die Dinge zu erzählen
und durch diese ein wenig mehr gehen

38
00:01:45,640 --> 00:01:49,180
langsamer als die anderen,
nur um hoffentlich den Kopf

39
00:01:49,180 --> 00:01:51,800
um die Ideen hinter merge sort.

40
00:01:51,800 --> 00:01:54,680
>> So haben wir das gleiche Array wie der
andere Sortieralgorithmus Videos

41
00:01:54,680 --> 00:01:57,120
Wenn Sie gesehen haben them--
ein Sechs-Element-Array.

42
00:01:57,120 --> 00:02:02,110
Und unsere Pseudocode ist hier sort
die linke Hälfte, sortieren Sie die rechte Hälfte,

43
00:02:02,110 --> 00:02:03,890
verschmelzen die beiden Hälften zusammen.

44
00:02:03,890 --> 00:02:09,770
Werfen wir also diese sehr dunklen Ziegelrot
Array und sortieren Sie die linke Hälfte.

45
00:02:09,770 --> 00:02:13,380
>> Also vorerst werden wir
das Zeug auf der rechten Seite zu ignorieren.

46
00:02:13,380 --> 00:02:15,740
Es ist da, aber wir sind
nicht bei diesem Schritt vor.

47
00:02:15,740 --> 00:02:18,220
Wir sind nicht in der Art,
rechte Hälfte des Arrays.

48
00:02:18,220 --> 00:02:21,037
Wir sind im Art die linke
Hälfte des Feldes.

49
00:02:21,037 --> 00:02:22,870
Und nur um
von einer etwas schwie

50
00:02:22,870 --> 00:02:26,480
klar, so verweise ich kann
in welchem ​​Schritt sind wir auf,

51
00:02:26,480 --> 00:02:29,800
Ich werde den Schalter
Farbe dieser Satz bis orange.

52
00:02:29,800 --> 00:02:33,190
Jetzt werden wir noch über die Gespräche
elbe linke Hälfte des ursprünglichen Arrays.

53
00:02:33,190 --> 00:02:38,520
Aber ich hoffe, dass durch die Möglichkeit,
beziehen sich auf die Farben der verschiedenen Elemente,

54
00:02:38,520 --> 00:02:40,900
es wird es ein wenig mehr zu machen
klar, was hier vor sich geht.

55
00:02:40,900 --> 00:02:43,270
>> OK, so jetzt haben wir ein
drei Elementanordnung.

56
00:02:43,270 --> 00:02:46,420
Wie können wir sortieren die linke Hälfte davon
Anordnung, die immer noch diese Stufe?

57
00:02:46,420 --> 00:02:49,400
Wir versuchen, die linke sortieren
Hälfte des Ziegelrot array--

58
00:02:49,400 --> 00:02:52,410
die linke Hälfte von denen
Ich habe jetzt orange gefärbt.

59
00:02:52,410 --> 00:02:54,840
>> Nun, wir könnten versuchen, und
Wiederholen Sie diesen Vorgang noch einmal.

60
00:02:54,840 --> 00:02:56,756
So sind wir immer noch in der
Mitte versucht zu sortieren

61
00:02:56,756 --> 00:02:58,700
die linke Hälfte des vollen Array.

62
00:02:58,700 --> 00:03:00,450
Die linke Hälfte des
Array, Ich werde einfach

63
00:03:00,450 --> 00:03:03,910
willkürlich entscheiden, dass die linke Hälfte
wird kleiner als die rechte Hälfte,

64
00:03:03,910 --> 00:03:06,550
denn dies geschieht,
bestehen aus drei Elementen.

65
00:03:06,550 --> 00:03:11,260
>> Und so werde ich sagen, dass die
linke Hälfte der linken Hälfte der Array-

66
00:03:11,260 --> 00:03:14,050
ist nur das Element fünf.

67
00:03:14,050 --> 00:03:18,360
Five, ein einzelnes Element
Array, wir wissen, wie es zu sortieren.

68
00:03:18,360 --> 00:03:21,615
Und so fünf sortiert ist.

69
00:03:21,615 --> 00:03:22,990
Wir sind gerade dabei, das zu erklären.

70
00:03:22,990 --> 00:03:24,890
Es ist ein Einzelelement-Array.

71
00:03:24,890 --> 00:03:29,015
>> Also haben wir jetzt nach der
linke Hälfte des linken half--

72
00:03:29,015 --> 00:03:33,190
oder besser gesagt, wir sortiert haben die
linke Hälfte der Orange.

73
00:03:33,190 --> 00:03:37,970
So, jetzt, um noch vollständig
linke Hälfte der Gesamt Arrays,

74
00:03:37,970 --> 00:03:43,481
wir brauchen, um die rechte Hälfte zu sortieren
der orange, oder diesem Zeug.

75
00:03:43,481 --> 00:03:44,230
Wie wir das machen?

76
00:03:44,230 --> 00:03:45,930
Nun, wir haben eine Zwei-Element-Array.

77
00:03:45,930 --> 00:03:50,470
So können wir die linke Hälfte sortieren
des Arrays, die zwei ist.

78
00:03:50,470 --> 00:03:52,090
Zwei ist ein einzelnes Element.

79
00:03:52,090 --> 00:03:55,890
So ist es standardmäßig sortiert.
Dann können wir die rechte Hälfte zu sortieren

80
00:03:55,890 --> 00:03:58,530
des Teils des Arrays, der einen.

81
00:03:58,530 --> 00:04:00,210
Das ist eine Art standardmäßig.

82
00:04:00,210 --> 00:04:03,610
>> Dies ist nun zum ersten Mal
haben wir eine Zusammenführungsschritt erreicht.

83
00:04:03,610 --> 00:04:06,135
Wir haben abgeschlossen, obwohl
wir jetzt Art verschachtelt down--

84
00:04:06,135 --> 00:04:08,420
und das ist die Art von tricky
Sache mit Rekursion,

85
00:04:08,420 --> 00:04:10,930
Sie Ihre halten müssen
Kopf darüber, wo wir sind.

86
00:04:10,930 --> 00:04:15,560
Deshalb haben wir uns irgendwie links
die Hälfte der orangen Teil.

87
00:04:15,560 --> 00:04:21,280
>> Und jetzt, die in der Mitte des Sortier sind
die rechte Hälfte der orangen Teil.

88
00:04:21,280 --> 00:04:25,320
Und in diesem Verfahren werden wir
nun zu den auf dem Schritt,

89
00:04:25,320 --> 00:04:27,850
verschmelzen die beiden Hälften zusammen.

90
00:04:27,850 --> 00:04:31,700
Wenn wir uns den beiden Hälften
des Arrays, sehen wir zwei und eins.

91
00:04:31,700 --> 00:04:33,880
Welches Element ist kleiner?

92
00:04:33,880 --> 00:04:35,160
Ein.

93
00:04:35,160 --> 00:04:36,760
>> Dann welches Element kleiner ist?

94
00:04:36,760 --> 00:04:38,300
Nun, es ist zwei oder nichts.

95
00:04:38,300 --> 00:04:39,910
So ist es zwei.

96
00:04:39,910 --> 00:04:43,690
So, jetzt, nur um wieder umrahmen
wo wir in Zusammenhang stehen,

97
00:04:43,690 --> 00:04:48,230
wir sortiert haben die
linke Hälfte der Orange

98
00:04:48,230 --> 00:04:49,886
und die rechte Hälfte des Ursprungs.

99
00:04:49,886 --> 00:04:52,510
Ich weiß, ich habe die Farbe verändert
wieder, aber das ist, wo wir waren.

100
00:04:52,510 --> 00:04:54,676
Und der Grund, warum ich tat dies,
Denn dieses Verfahren

101
00:04:54,676 --> 00:04:57,870
werde weitermachen, Iteration nach unten.

102
00:04:57,870 --> 00:05:00,500
Wir haben die linken sortiert
die Hälfte der ehemaligen Orangen

103
00:05:00,500 --> 00:05:02,590
und die rechte Hälfte des ehemaligen Orange.

104
00:05:02,590 --> 00:05:05,620
>> Jetzt müssen wir diejenigen, verschmelzen
zwei Hälften zu zusammen.

105
00:05:05,620 --> 00:05:07,730
Das ist der Schritt, den wir unterwegs sind.

106
00:05:07,730 --> 00:05:11,440
So dass wir alle das betrachten
Elemente, die nun grün sind,

107
00:05:11,440 --> 00:05:12,972
die linke Hälfte des ursprünglichen Arrays.

108
00:05:12,972 --> 00:05:14,680
Und wir zusammenführen denen
Verwendung des gleichen Verfahrens

109
00:05:14,680 --> 00:05:18,660
wir für das Zusammenführen zweier tat
und vor einem nur einen Augenblick.

110
00:05:18,660 --> 00:05:23,080
>> Die linke Hälfte, die kleinste
Element auf der linken Hälfte ist fünf.

111
00:05:23,080 --> 00:05:25,620
Das kleinste Element
die rechte Hälfte gehört.

112
00:05:25,620 --> 00:05:27,370
Welche dieser kleiner ist?

113
00:05:27,370 --> 00:05:29,260
Ein.

114
00:05:29,260 --> 00:05:32,250
>> Das kleinste Element
die linke Hälfte ist fünf.

115
00:05:32,250 --> 00:05:35,540
Das kleinste Element
die rechte Hälfte ist zwei.

116
00:05:35,540 --> 00:05:36,970
Was ist der kleinste?

117
00:05:36,970 --> 00:05:38,160
Zwei.

118
00:05:38,160 --> 00:05:41,540
Und dann schließlich fünf
nichts, können wir sagen, fünf.

119
00:05:41,540 --> 00:05:43,935
>> OK, so dass große Bild, lassen Sie uns
machen Sie eine Pause für eine Sekunde

120
00:05:43,935 --> 00:05:46,080
und herausfinden, wo wir sind.

121
00:05:46,080 --> 00:05:48,580
Wenn wir aus gestartet
Anbeginn wir

122
00:05:48,580 --> 00:05:51,640
haben jetzt abgeschlossen
die Gesamtanordnung nur

123
00:05:51,640 --> 00:05:53,810
einen Schritt des Pseudocode.

124
00:05:53,810 --> 00:05:56,645
Wir haben nach der
linken Hälfte des Arrays.

125
00:05:56,645 --> 00:05:59,490
>> Daran erinnern, dass der Original
Um fünf war, zwei, eins.

126
00:05:59,490 --> 00:06:02,570
Indem wir durch diesen Prozess
und nisten nach unten und wiederholen,

127
00:06:02,570 --> 00:06:05,990
Weiterbildung, um das Problem zu brechen
sich in immer kleinere Teile,

128
00:06:05,990 --> 00:06:09,670
Wir haben jetzt
Schritt eine der Pseudocode

129
00:06:09,670 --> 00:06:13,940
für die gesamte Ausgangs Array.

130
00:06:13,940 --> 00:06:16,670
Wir haben seine linke Hälfte sortiert.

131
00:06:16,670 --> 00:06:18,670
>> So, jetzt wollen wir es einfrieren.

132
00:06:18,670 --> 00:06:23,087
Und jetzt ist irgendwie das Recht lassen
die Hälfte des ursprünglichen Arrays.

133
00:06:23,087 --> 00:06:25,670
Und wir werden, dass durch zu tun
gehen durch die gleiche iterative

134
00:06:25,670 --> 00:06:30,630
Prozess der Unterbrechung Dinge nach unten
und dann zusammen Zusammenlegung.

135
00:06:30,630 --> 00:06:34,290
>> So ist die linke Hälfte des
rot, oder die linke Hälfte

136
00:06:34,290 --> 00:06:38,830
der rechten Hälfte des ursprünglichen
Array, werde ich sagen, ist drei.

137
00:06:38,830 --> 00:06:40,312
Auch hier bin ich, hier konsequent.

138
00:06:40,312 --> 00:06:42,020
Wenn Sie eine ungerade haben
Anzahl der Elemente, so

139
00:06:42,020 --> 00:06:44,478
spielt eigentlich keine Rolle, ob
Sie links ein kleiner machen

140
00:06:44,478 --> 00:06:45,620
oder die richtige kleiner.

141
00:06:45,620 --> 00:06:49,230
>> Was zählt, ist, dass, wann immer Sie
begegnen diesem Problem bei der Durchführung

142
00:06:49,230 --> 00:06:51,422
eine Zusammenführung, Sie müssen konsequent sein.

143
00:06:51,422 --> 00:06:53,505
Entweder müssen immer
Sie links Seite kleiner

144
00:06:53,505 --> 00:06:55,421
oder immer brauchen, um
die rechte Seite kleiner.

145
00:06:55,421 --> 00:06:57,720
Hier habe ich immer gewählt haben
machen die linke Seite kleiner

146
00:06:57,720 --> 00:07:04,380
wenn meine Array oder meine
Sub-Array ist aus einer ungeraden Größe.

147
00:07:04,380 --> 00:07:07,420
>> Drei ein einzelnes Element ist,
und so sortiert wird.

148
00:07:07,420 --> 00:07:10,860
Wir haben diese Annahme Leveraged
in unserer gesamten Prozess so weit.

149
00:07:10,860 --> 00:07:15,020
So, jetzt ist irgendwie das Recht lassen
Hälfte der rechten Hälfte,

150
00:07:15,020 --> 00:07:18,210
oder die rechte Hälfte des roten.

151
00:07:18,210 --> 00:07:20,390
>> Auch hier müssen wir diese gespalten.

152
00:07:20,390 --> 00:07:21,910
Dies ist nicht ein einzelnes Element-Array.

153
00:07:21,910 --> 00:07:23,970
Wir können uns nicht erklären, es sortiert.

154
00:07:23,970 --> 00:07:27,060
Und so zuerst, wir gehen
um die linke Hälfte zu sortieren.

155
00:07:27,060 --> 00:07:31,620
>> Die linke Hälfte ist ein einzelnes Element,
also ist es Art von standardmäßig.

156
00:07:31,620 --> 00:07:34,840
Dann werden wir das Recht zu sortieren
Hälfte, die ein einzelnes Element ist.

157
00:07:34,840 --> 00:07:41,250
Es ist standardmäßig sortiert. Und jetzt,
Wir können diese beiden miteinander verschmelzen.

158
00:07:41,250 --> 00:07:45,820
Vier kleiner ist, und
dann sechs ist kleiner.

159
00:07:45,820 --> 00:07:48,870
>> Wieder was haben wir an dieser Stelle getan?

160
00:07:48,870 --> 00:07:52,512
Wir haben die linken sortiert
die Hälfte der in der rechten Hälfte.

161
00:07:52,512 --> 00:07:54,720
Oder gehen zurück auf die ursprüngliche
Farben, die dort waren,

162
00:07:54,720 --> 00:07:57,875
wir haben die linken sortiert
Hälfte des weicheren rot.

163
00:07:57,875 --> 00:08:00,416
Es war ursprünglich ein dunklem Backstein
rot und jetzt ist es eine weichere rot,

164
00:08:00,416 --> 00:08:02,350
oder es war ein weicher rot.

165
00:08:02,350 --> 00:08:05,145
>> Und dann haben wir sortiert haben die
rechte Hälfte des weicheren rot.

166
00:08:05,145 --> 00:08:08,270
Nun gut, sie sind wieder grün, nur
weil wir durch einen Prozess gehen.

167
00:08:08,270 --> 00:08:10,720
Und wir haben zu wiederholen,
das immer und immer.

168
00:08:10,720 --> 00:08:14,695
>> So, jetzt können wir diese zusammenführen
zwei Hälften zusammen.

169
00:08:14,695 --> 00:08:15,820
Und das ist, was wir hier tun.

170
00:08:15,820 --> 00:08:17,653
Also die schwarze Linie nur
unterteilt die linke Hälfte

171
00:08:17,653 --> 00:08:19,690
und die rechte Hälfte dieser Art teil.

172
00:08:19,690 --> 00:08:24,310
>> Wir vergleichen den kleinsten Wert
auf der linken Seite des array--

173
00:08:24,310 --> 00:08:26,710
oder entschuldigen Sie mich, den kleinsten
Wert der linken Hälfte

174
00:08:26,710 --> 00:08:30,790
auf den kleinsten Wert der rechten
Halb und feststellen, dass drei kleiner ist.

175
00:08:30,790 --> 00:08:32,530
Und jetzt ein bisschen wie eine Optimierung, nicht wahr?

176
00:08:32,530 --> 00:08:35,175
Es gibt eigentlich nichts
nach links auf der linken Seite.

177
00:08:35,175 --> 00:08:37,440
>> Es gibt noch nichts
auf der linken Seite,

178
00:08:37,440 --> 00:08:40,877
so können wir effizient
nur move-- können wir erklären,

179
00:08:40,877 --> 00:08:42,960
der Rest ist eigentlich
sortiert und nur heften

180
00:08:42,960 --> 00:08:45,126
auf, denn es gibt nichts,
sonst gegen zu vergleichen.

181
00:08:45,126 --> 00:08:49,140
Und wir wissen, dass die rechte Seite
von der rechten Seite sortiert wird.

182
00:08:49,140 --> 00:08:52,770
>> OK, so jetzt ist wieder einfrieren lassen und
herauszufinden, wo wir in der Geschichte sind.

183
00:08:52,770 --> 00:08:56,120
In der Gesamtanordnung,
Was haben wir erreicht?

184
00:08:56,120 --> 00:08:58,790
Wir haben tatsächlich zu erreichen
Jetzt die Schritte eins und Schritt zwei.

185
00:08:58,790 --> 00:09:03,300
Wir sortiert die linke Hälfte, und
wir nach die rechte Hälfte.

186
00:09:03,300 --> 00:09:08,210
>> So, jetzt ist für uns alles, was bleibt
um diese beiden Hälften miteinander verschmelzen.

187
00:09:08,210 --> 00:09:11,670
So dass wir vergleichen die niedrigsten bewertet
Element jeder Hälfte der Anordnung

188
00:09:11,670 --> 00:09:13,510
der Reihe nach und gehen.

189
00:09:13,510 --> 00:09:16,535
Eine weniger als drei ist, so geht man.

190
00:09:16,535 --> 00:09:19,770
>> Zwei weniger als drei beträgt, so dass zwei hinausgeht.

191
00:09:19,770 --> 00:09:22,740
Drei weniger als 5, so dass drei geht.

192
00:09:22,740 --> 00:09:25,820
Vier kleiner ist als 5, so vier geht.

193
00:09:25,820 --> 00:09:30,210
Dann fünf kleiner als sechs,
und sechs ist alles, was bleibt.

194
00:09:30,210 --> 00:09:31,820
>> Nun, ich weiß, das war eine Menge von Schritten.

195
00:09:31,820 --> 00:09:33,636
Und wir haben eine Menge links
Speicher in unserem Kielwasser.

196
00:09:33,636 --> 00:09:35,260
Und das ist, was die grauen Quadrate sind.

197
00:09:35,260 --> 00:09:40,540
Und es ist wahrscheinlich das Gefühl, dass fand ein
viel länger als Insertion Sort, bubble

198
00:09:40,540 --> 00:09:42,660
sortieren oder Auswahl sort.

199
00:09:42,660 --> 00:09:45,330
>> Aber eigentlich, denn ein
Viele dieser Prozesse

200
00:09:45,330 --> 00:09:48,260
werden gleichzeitig Zeit-- geschieht
die etwas, das wir ist, wieder,

201
00:09:48,260 --> 00:09:51,100
reden, wenn wir sprechen
Rekursion in einer zukünftigen video--

202
00:09:51,100 --> 00:09:53,799
dieser Algorithmus tatsächlich
klar ist grundsätzlich

203
00:09:53,799 --> 00:09:55,590
anders als alles,
wir zuvor gesehen haben

204
00:09:55,590 --> 00:09:58,820
sondern auch wesentlich
effizienter.

205
00:09:58,820 --> 00:09:59,532
>> Warum ist das so?

206
00:09:59,532 --> 00:10:01,240
Nun, im schlimmsten
Case-Szenario, haben wir

207
00:10:01,240 --> 00:10:04,830
um n Elemente aufzuteilen
und dann rekombinieren sie.

208
00:10:04,830 --> 00:10:06,680
Aber wenn wir rekombinieren
ihnen, was wir tun,

209
00:10:06,680 --> 00:10:11,110
ist im Grunde eine Verdoppelung der
Größe der kleineren Arrays.

210
00:10:11,110 --> 00:10:14,260
Wir haben eine Reihe von einem Element
Arrays, die wir effektiv

211
00:10:14,260 --> 00:10:16,290
kombiniert in zwei Elementanordnungen.

212
00:10:16,290 --> 00:10:18,590
Und dann nehmen wir diejenigen,
zwei Elementanordnungen

213
00:10:18,590 --> 00:10:21,890
und miteinander kombinieren sie zu
Vierelement-Arrays, und so weiter,

214
00:10:21,890 --> 00:10:26,130
und so weiter, und so weiter, bis wir
eine einzige n Elementanordnung.

215
00:10:26,130 --> 00:10:29,910
>> Aber wie viele Dopplungen
dauert es, bis zu n zu bekommen?

216
00:10:29,910 --> 00:10:31,460
Denken Sie zurück an das Telefonbuch Beispiel.

217
00:10:31,460 --> 00:10:34,490
Wie oft müssen wir zu zerreißen haben
das Telefonbuch in der Hälfte, wie viele

218
00:10:34,490 --> 00:10:38,370
Mal wollen wir das Telefonbuch zerreißen haben
in der Hälfte, wenn die Größe des Telefonbuchs

219
00:10:38,370 --> 00:10:39,680
verdoppelt?

220
00:10:39,680 --> 00:10:41,960
Es gibt nur ein, nicht wahr?

221
00:10:41,960 --> 00:10:45,360
>> Es gibt also eine Art von
logarithmische Element.

222
00:10:45,360 --> 00:10:48,590
Wir haben aber auch noch zumindest
Blick auf alle der n Elemente.

223
00:10:48,590 --> 00:10:53,860
Also im ungünstigsten Fall
Mergesort läuft in n log n.

224
00:10:53,860 --> 00:10:56,160
Wir haben, zu betrachten
alle der n Elemente,

225
00:10:56,160 --> 00:11:02,915
und wir, sie zu kombinieren haben
zusammen in log n Gruppen von Schritten.

226
00:11:02,915 --> 00:11:05,290
Im besten Fall,
das Array perfekt sortiert.

227
00:11:05,290 --> 00:11:06,300
Das ist großartig.

228
00:11:06,300 --> 00:11:09,980
Aber auf dem Algorithmus haben wir hier,
wir haben immer noch zu spalten und zu rekombinieren.

229
00:11:09,980 --> 00:11:13,290
Obwohl in diesem Fall wird das
Rekombination ist eine Art unwirksam.

230
00:11:13,290 --> 00:11:14,720
Es ist nicht erforderlich.

231
00:11:14,720 --> 00:11:17,580
Aber wir haben noch durchgehen
der gesamte Prozess sowieso.

232
00:11:17,580 --> 00:11:21,290
>> So im besten Fall
und im schlimmsten Fall

233
00:11:21,290 --> 00:11:24,970
Dieser Algorithmus läuft in n log n Zeit.

234
00:11:24,970 --> 00:11:29,130
Merge sort ist auf jeden Fall ein bisschen schwieriger
als die anderen Hauptsortieralgorithmen

235
00:11:29,130 --> 00:11:33,470
wir über CS50 gesprochen haben, ist aber
wesentlich leistungsfähiger.

236
00:11:33,470 --> 00:11:35,400
>> Und so, wenn Sie überhaupt finden
Gelegenheit, um es brauchen

237
00:11:35,400 --> 00:11:38,480
oder, es zu benutzen, um eine Art
großen Datensatz, bekommen

238
00:11:38,480 --> 00:11:41,940
Ihren Kopf um die Idee der Rekursion
sein wird, wirklich mächtig.

239
00:11:41,940 --> 00:11:45,270
Und es geht um Ihre
Programme wirklich viel effizienter

240
00:11:45,270 --> 00:11:48,700
mit Mergesort gegen alles andere.

241
00:11:48,700 --> 00:11:49,640
Ich bin Doug Lloyd.

242
00:11:49,640 --> 00:11:51,970
Dies ist CS50.

243
00:11:51,970 --> 00:11:53,826