1
00:00:00,000 --> 00:00:04,419
>> [REPRODUCCIÓN DE MÚSICA]

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

3
00:00:05,401 --> 00:00:08,460
>> DOUG LLOYD: OK, por lo que una fusión
especie es otro algoritmo

4
00:00:08,460 --> 00:00:11,200
que podemos utilizar para solucionar
los elementos de una matriz.

5
00:00:11,200 --> 00:00:14,480
Pero como veremos, tiene un
diferencia muy fundamental

6
00:00:14,480 --> 00:00:17,850
desde la selección del tipo, burbuja
ordenar y ordenación por inserción

7
00:00:17,850 --> 00:00:20,280
que hacen que sea realmente muy inteligente.

8
00:00:20,280 --> 00:00:24,290
>> La idea básica detrás de la fusión
clase es para ordenar arrays más pequeños

9
00:00:24,290 --> 00:00:27,430
y luego combinar los arrays
juntos, o fusionar ellos--

10
00:00:27,430 --> 00:00:31,440
de ahí el nombre-- en forma ordenada.

11
00:00:31,440 --> 00:00:34,230
La forma en que se funden especie hace
esto es mediante el aprovechamiento de una herramienta

12
00:00:34,230 --> 00:00:37,290
llama recursividad, que es lo que
vamos a estar hablando de pronto,

13
00:00:37,290 --> 00:00:39,720
pero en realidad no hemos hablado todavía.

14
00:00:39,720 --> 00:00:43,010
>> Esta es la idea básica detrás de mezcla tipo.

15
00:00:43,010 --> 00:00:46,320
Ordene la mitad izquierda de la matriz,
suponiendo que n es mayor que 1.

16
00:00:46,320 --> 00:00:49,980
Y lo que quiero decir cuando digo
suponiendo que n es mayor que 1, es decir,

17
00:00:49,980 --> 00:00:53,970
Creo que podemos estar de acuerdo que si una matriz
sólo se compone de un único elemento,

18
00:00:53,970 --> 00:00:54,680
se arregló.

19
00:00:54,680 --> 00:00:56,560
En realidad no necesitamos
que hacer nada para él.

20
00:00:56,560 --> 00:00:58,059
Sólo podemos declararlo a clasificar.

21
00:00:58,059 --> 00:01:00,110
No es más que un solo elemento.

22
00:01:00,110 --> 00:01:03,610
>> Así que el pseudocódigo, de nuevo, es
ordenar la mitad izquierda de la matriz,

23
00:01:03,610 --> 00:01:08,590
a continuación, ordenar la mitad derecha de la matriz,
luego fusionar las dos mitades.

24
00:01:08,590 --> 00:01:11,040
Ahora, ya que podría ser
pensar, es como que acaba de

25
00:01:11,040 --> 00:01:14,080
suena como usted está poniendo fuera el--
usted no está realmente haciendo nada.

26
00:01:14,080 --> 00:01:16,330
¿Estás diciendo que ordenar la izquierda
medio, más o menos la mitad derecha,

27
00:01:16,330 --> 00:01:19,335
pero no se está diciendo
mí cómo lo estás haciendo.

28
00:01:19,335 --> 00:01:22,220
>> Pero recuerde que mientras
una matriz es un solo elemento,

29
00:01:22,220 --> 00:01:23,705
podemos declarar lo arregló.

30
00:01:23,705 --> 00:01:25,330
Entonces sólo podemos combinarlos.

31
00:01:25,330 --> 00:01:27,788
Y eso es en realidad el
idea fundamental detrás de combinación de clase,

32
00:01:27,788 --> 00:01:31,150
es romper hacia abajo para que
las matrices son de talla única.

33
00:01:31,150 --> 00:01:33,430
Y luego vuelve a generar a partir de ahí.

34
00:01:33,430 --> 00:01:35,910
>> Merge Sort es definitivamente
un algoritmo complicado.

35
00:01:35,910 --> 00:01:38,210
Y también es un poco
complicado de visualizar.

36
00:01:38,210 --> 00:01:41,870
Así que es de esperar, la visualización que
tiene aquí le ayudará a lo sigue.

37
00:01:41,870 --> 00:01:45,640
Y voy a intentar mi mejor esfuerzo para narrar las cosas
y proceder a través de esto un poco más

38
00:01:45,640 --> 00:01:49,180
lentamente que los demás
sólo para obtener espero tu cabeza

39
00:01:49,180 --> 00:01:51,800
alrededor de las ideas detrás de mezcla tipo.

40
00:01:51,800 --> 00:01:54,680
>> Así que tenemos la misma matriz como la
otros vídeos del algoritmo de clasificación

41
00:01:54,680 --> 00:01:57,120
ellos-- si has visto
una matriz de seis elementos.

42
00:01:57,120 --> 00:02:02,110
Y nuestro código pseudocódigo aquí es una especie
la mitad izquierda, ordenar la mitad derecha,

43
00:02:02,110 --> 00:02:03,890
fusionar las dos mitades juntas.

44
00:02:03,890 --> 00:02:09,770
Así que tomemos este ladrillo rojo muy oscuro
matriz y ordenar el medio que queda de ella.

45
00:02:09,770 --> 00:02:13,380
>> Así que por el momento, vamos
hacer caso omiso de las cosas a la derecha.

46
00:02:13,380 --> 00:02:15,740
Está ahí, pero estamos
no en ese paso todavía.

47
00:02:15,740 --> 00:02:18,220
No estamos en la clase
media derecha de la matriz.

48
00:02:18,220 --> 00:02:21,037
Estamos en una especie de la izquierda
medio de la matriz.

49
00:02:21,037 --> 00:02:22,870
Y sólo por el bien
de ser un poco más

50
00:02:22,870 --> 00:02:26,480
claro, así que me puedo referir
a lo que el paso que estamos en,

51
00:02:26,480 --> 00:02:29,800
Voy a cambiar la
color de este conjunto de naranja.

52
00:02:29,800 --> 00:02:33,190
Ahora, todavía estamos hablando de la
misma mitad izquierda de la matriz original.

53
00:02:33,190 --> 00:02:38,520
Pero espero que al ser capaces de
referirse a los colores de diversos artículos,

54
00:02:38,520 --> 00:02:40,900
que va a hacer un poco más
aclarar lo que está pasando aquí.

55
00:02:40,900 --> 00:02:43,270
>> OK, así que ahora tenemos una
de tres conjunto de elementos.

56
00:02:43,270 --> 00:02:46,420
¿Cómo ordenar la media izquierda de esta
array, que sigue siendo este paso?

57
00:02:46,420 --> 00:02:49,400
Estamos tratando de ordenar la izquierda
medio del array-- ladrillo rojo

58
00:02:49,400 --> 00:02:52,410
la mitad izquierda de los cuales
Ahora he de color naranja.

59
00:02:52,410 --> 00:02:54,840
>> Bueno, podríamos tratar de
repetir este proceso otra vez.

60
00:02:54,840 --> 00:02:56,756
Así que todavía estamos en el
medio de tratar de clasificar

61
00:02:56,756 --> 00:02:58,700
la mitad izquierda de la matriz completa.

62
00:02:58,700 --> 00:03:00,450
La mitad izquierda de la
matriz, sólo voy

63
00:03:00,450 --> 00:03:03,910
para decidir arbitrariamente que la mitad izquierda
será menor que la mitad derecha,

64
00:03:03,910 --> 00:03:06,550
porque esto le sucede a
constará de tres elementos.

65
00:03:06,550 --> 00:03:11,260
>> Y por lo que voy a decir que la
media izquierda de la mitad izquierda de la matriz

66
00:03:11,260 --> 00:03:14,050
es sólo el elemento de cinco.

67
00:03:14,050 --> 00:03:18,360
Five, siendo un solo elemento
matriz, sabemos cómo arreglarlo.

68
00:03:18,360 --> 00:03:21,615
Y así, de cinco se ordena.

69
00:03:21,615 --> 00:03:22,990
Sólo vamos a declarar eso.

70
00:03:22,990 --> 00:03:24,890
Es un solo elemento de la matriz.

71
00:03:24,890 --> 00:03:29,015
>> Así que ahora hemos solucionaron el
mitad izquierda de la izquierda half--

72
00:03:29,015 --> 00:03:33,190
o más bien, hemos solucionaron el
mitad izquierda de la naranja.

73
00:03:33,190 --> 00:03:37,970
Así que ahora, con el fin de todavía completa
mitad izquierda de la matriz global,

74
00:03:37,970 --> 00:03:43,481
tenemos que ordenar la mitad derecha
de la naranja, o estas cosas.

75
00:03:43,481 --> 00:03:44,230
¿Cómo lo hacemos?

76
00:03:44,230 --> 00:03:45,930
Bueno, tenemos una matriz de dos elementos.

77
00:03:45,930 --> 00:03:50,470
Así que podemos ordenar la media izquierda
de la matriz, que es de dos.

78
00:03:50,470 --> 00:03:52,090
Dos es un solo elemento.

79
00:03:52,090 --> 00:03:55,890
Así que ha ordenado de forma predeterminada.
Entonces podemos ordenar la mitad derecha

80
00:03:55,890 --> 00:03:58,530
de esa porción de la matriz, el uno.

81
00:03:58,530 --> 00:04:00,210
Eso es una especie de forma predeterminada.

82
00:04:00,210 --> 00:04:03,610
>> Esta es ahora la primera vez
hemos llegado a una etapa de mezcla.

83
00:04:03,610 --> 00:04:06,135
Hemos completado, aunque
ahora estamos tipo de anidado down--

84
00:04:06,135 --> 00:04:08,420
y eso es una especie de la difícil
cosa con la recursividad es,

85
00:04:08,420 --> 00:04:10,930
usted necesita para mantener su
cabeza acerca de dónde estamos.

86
00:04:10,930 --> 00:04:15,560
Para ello hemos especie de la izquierda
medio de la porción de naranja.

87
00:04:15,560 --> 00:04:21,280
>> Y ahora, estamos en el medio de la clasificación
la mitad derecha de la parte naranja.

88
00:04:21,280 --> 00:04:25,320
Y en ese proceso, estamos
ahora a punto de estar en el paso,

89
00:04:25,320 --> 00:04:27,850
fusionar las dos mitades juntas.

90
00:04:27,850 --> 00:04:31,700
Cuando nos fijamos en las dos mitades
de la matriz, vemos dos y uno.

91
00:04:31,700 --> 00:04:33,880
¿Qué elemento es menor?

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

93
00:04:35,160 --> 00:04:36,760
>> Entonces qué elemento es más pequeño?

94
00:04:36,760 --> 00:04:38,300
Bueno, es dos o nada.

95
00:04:38,300 --> 00:04:39,910
Así que es dos.

96
00:04:39,910 --> 00:04:43,690
Así que ahora, sólo para enmarcar de nuevo
donde estamos en contexto,

97
00:04:43,690 --> 00:04:48,230
hemos ordenado la
mitad izquierda de la naranja

98
00:04:48,230 --> 00:04:49,886
y la mitad derecha del origen.

99
00:04:49,886 --> 00:04:52,510
Sé que he cambiado los colores
de nuevo, pero eso es donde estábamos.

100
00:04:52,510 --> 00:04:54,676
Y la razón por la que hizo esto
es porque este proceso es

101
00:04:54,676 --> 00:04:57,870
va a seguir adelante, iterando hacia abajo.

102
00:04:57,870 --> 00:05:00,500
Hemos solucionaron la izquierda
la mitad de la antigua naranja

103
00:05:00,500 --> 00:05:02,590
y la mitad derecha de la antigua naranja.

104
00:05:02,590 --> 00:05:05,620
>> Ahora, tenemos que combinar los
dos mitades también.

105
00:05:05,620 --> 00:05:07,730
Ese es el paso que estamos en.

106
00:05:07,730 --> 00:05:11,440
Así tenemos en cuenta la totalidad de la
elementos que ahora son de color verde,

107
00:05:11,440 --> 00:05:12,972
la mitad izquierda de la matriz original.

108
00:05:12,972 --> 00:05:14,680
Y nos fusionamos los
utilizando el mismo proceso

109
00:05:14,680 --> 00:05:18,660
lo hicimos para la fusión de dos
y hace un un momento.

110
00:05:18,660 --> 00:05:23,080
>> La mitad izquierda, la más pequeña
elemento en la mitad izquierda es de cinco.

111
00:05:23,080 --> 00:05:25,620
El componente más pequeño de
la mitad derecha es uno.

112
00:05:25,620 --> 00:05:27,370
¿Cuál de ellos es más pequeño?

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

114
00:05:29,260 --> 00:05:32,250
>> El componente más pequeño de
la mitad izquierda es de cinco.

115
00:05:32,250 --> 00:05:35,540
El componente más pequeño de
la mitad derecha es de dos.

116
00:05:35,540 --> 00:05:36,970
¿Cuál es el más pequeño?

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

118
00:05:38,160 --> 00:05:41,540
Y luego, por último, cinco y
nada, podemos decir cinco.

119
00:05:41,540 --> 00:05:43,935
>> OK, la imagen tan grande, vamos a
tomar un descanso por un segundo

120
00:05:43,935 --> 00:05:46,080
y averiguar dónde estamos.

121
00:05:46,080 --> 00:05:48,580
Si partimos de
el principio, nos

122
00:05:48,580 --> 00:05:51,640
ahora se han completado para
la matriz global justo

123
00:05:51,640 --> 00:05:53,810
un paso del código pseudocódigo aquí.

124
00:05:53,810 --> 00:05:56,645
Hemos ordenado la
media izquierda de la matriz.

125
00:05:56,645 --> 00:05:59,490
>> Recordemos que el original
orden era de cinco, dos, uno.

126
00:05:59,490 --> 00:06:02,570
Al pasar por este proceso
y anidando abajo y repetir,

127
00:06:02,570 --> 00:06:05,990
continua para romper el problema
en partes cada vez más pequeñas,

128
00:06:05,990 --> 00:06:09,670
ahora hemos completado
paso uno del pseudocódigo

129
00:06:09,670 --> 00:06:13,940
para toda la matriz de partida.

130
00:06:13,940 --> 00:06:16,670
Hemos ordenado su mitad izquierda.

131
00:06:16,670 --> 00:06:18,670
>> Así que ahora vamos a congelar allí.

132
00:06:18,670 --> 00:06:23,087
Y ahora vamos a ordenar la derecha
la mitad de la matriz original.

133
00:06:23,087 --> 00:06:25,670
Y vamos a hacer eso por
pasando por el mismo iterativo

134
00:06:25,670 --> 00:06:30,630
proceso de romper las cosas
y luego fusionarlos juntos.

135
00:06:30,630 --> 00:06:34,290
>> Así que la mitad izquierda de la
rojo, o la mitad izquierda

136
00:06:34,290 --> 00:06:38,830
de la mitad derecha del original
matriz, que voy a decir es tres.

137
00:06:38,830 --> 00:06:40,312
Una vez más, estoy siendo coherente aquí.

138
00:06:40,312 --> 00:06:42,020
Si usted tiene un extraño
número de elementos,

139
00:06:42,020 --> 00:06:44,478
en realidad no importa si
a tomar el de la izquierda más pequeña

140
00:06:44,478 --> 00:06:45,620
o el derecho de un menor.

141
00:06:45,620 --> 00:06:49,230
>> Lo que importa es que cada vez que
encontrar este problema en la realización de

142
00:06:49,230 --> 00:06:51,422
una fusión, tiene que ser coherente.

143
00:06:51,422 --> 00:06:53,505
Usted bien siempre hay que
hacer un lado izquierdo más pequeño

144
00:06:53,505 --> 00:06:55,421
o siempre que tenga que hacer
el lado derecho más pequeño.

145
00:06:55,421 --> 00:06:57,720
Aquí, he optado por siempre
hacer que el lado izquierdo más pequeño

146
00:06:57,720 --> 00:07:04,380
cuando mi matriz, o de mi
sub-matriz, es de un tamaño impar.

147
00:07:04,380 --> 00:07:07,420
>> Tres es un solo elemento,
y por lo que se ordena.

148
00:07:07,420 --> 00:07:10,860
Hemos aprovechado esa suposición
lo largo de todo nuestro proceso hasta el momento.

149
00:07:10,860 --> 00:07:15,020
Así que ahora vamos a ordenar la derecha
la mitad de la mitad derecha,

150
00:07:15,020 --> 00:07:18,210
o la mitad derecha de la roja.

151
00:07:18,210 --> 00:07:20,390
>> Una vez más, tenemos que dividir esto.

152
00:07:20,390 --> 00:07:21,910
Esto no es un único elemento de la matriz.

153
00:07:21,910 --> 00:07:23,970
No podemos declarar lo arregló.

154
00:07:23,970 --> 00:07:27,060
Y así, en primer lugar, vamos
para ordenar la mitad izquierda.

155
00:07:27,060 --> 00:07:31,620
>> La mitad izquierda es un solo elemento,
por lo que es una especie de forma predeterminada.

156
00:07:31,620 --> 00:07:34,840
Entonces vamos a ordenar la derecha
medio, que es un solo elemento.

157
00:07:34,840 --> 00:07:41,250
Está ordenada por defecto. Y ahora,
podemos combinar los dos juntos.

158
00:07:41,250 --> 00:07:45,820
Cuatro es más pequeño, y
a continuación, seis es más pequeño.

159
00:07:45,820 --> 00:07:48,870
>> Una vez más, ¿qué hemos hecho en este punto?

160
00:07:48,870 --> 00:07:52,512
Hemos solucionaron la izquierda
la mitad de la mitad derecha.

161
00:07:52,512 --> 00:07:54,720
O volver a la original
colores que estaban allí,

162
00:07:54,720 --> 00:07:57,875
hemos solucionaron la izquierda
medio del rojo más suave.

163
00:07:57,875 --> 00:08:00,416
Originalmente fue un ladrillo oscuro
rojo y ahora es un rojo más suave,

164
00:08:00,416 --> 00:08:02,350
o que era un rojo más suave.

165
00:08:02,350 --> 00:08:05,145
>> Y luego hemos solucionaron el
mitad derecha del rojo más suave.

166
00:08:05,145 --> 00:08:08,270
Ahora, bien, son verdes de nuevo, sólo
porque vamos a través de un proceso.

167
00:08:08,270 --> 00:08:10,720
Y tenemos que repetir
esto una y otra.

168
00:08:10,720 --> 00:08:14,695
>> Así que ahora podemos combinar los
dos mitades.

169
00:08:14,695 --> 00:08:15,820
Y eso es lo que hacemos aquí.

170
00:08:15,820 --> 00:08:17,653
Así que la línea de negro solo
dividido a la mitad izquierda

171
00:08:17,653 --> 00:08:19,690
y la mitad derecha de esta parte de clasificación.

172
00:08:19,690 --> 00:08:24,310
>> Comparamos el valor más pequeño
en el lado izquierdo de la array--

173
00:08:24,310 --> 00:08:26,710
o perdón, la más pequeña
valor de la mitad izquierda

174
00:08:26,710 --> 00:08:30,790
al valor más pequeño de la derecha
medio y encontrar que tres es más pequeño.

175
00:08:30,790 --> 00:08:32,530
Y ahora un poco de una optimización, ¿verdad?

176
00:08:32,530 --> 00:08:35,175
En realidad hay nada
a la izquierda en el lado izquierdo.

177
00:08:35,175 --> 00:08:37,440
>> No hay nada restante
En el lado izquierdo,

178
00:08:37,440 --> 00:08:40,877
para que podamos de manera eficiente
simplemente move-- podemos declarar

179
00:08:40,877 --> 00:08:42,960
el resto de él es en realidad
ordenado y justo virar

180
00:08:42,960 --> 00:08:45,126
en adelante, porque no hay nada
otra cosa que comparar.

181
00:08:45,126 --> 00:08:49,140
Y sabemos que el lado derecho
del lado derecho está ordenada.

182
00:08:49,140 --> 00:08:52,770
>> OK, así que ahora vamos a congelar de nuevo y
averiguar dónde estamos en la historia.

183
00:08:52,770 --> 00:08:56,120
En la matriz general,
¿qué hemos logrado?

184
00:08:56,120 --> 00:08:58,790
De hecho, hemos logramos
ahora los pasos uno y el paso dos.

185
00:08:58,790 --> 00:09:03,300
Clasificamos la mitad izquierda, y
nos lo solucionaron la mitad derecha.

186
00:09:03,300 --> 00:09:08,210
>> Así que ahora, todo lo que queda es para nosotros
fusionar esas dos mitades.

187
00:09:08,210 --> 00:09:11,670
Así comparamos el más bajo valorado
elemento de cada medio de la matriz

188
00:09:11,670 --> 00:09:13,510
a su vez, y proceder.

189
00:09:13,510 --> 00:09:16,535
Una de ellas es inferior a tres, por lo que uno va.

190
00:09:16,535 --> 00:09:19,770
>> Dos es inferior a tres, así que dos va.

191
00:09:19,770 --> 00:09:22,740
Tres es inferior a 5, así que tres va.

192
00:09:22,740 --> 00:09:25,820
Cuatro es inferior a 5, por lo que va de cuatro.

193
00:09:25,820 --> 00:09:30,210
Luego de cinco es menos de seis,
y seis es todo lo que queda.

194
00:09:30,210 --> 00:09:31,820
>> Ahora, lo sé, que era un montón de pasos.

195
00:09:31,820 --> 00:09:33,636
Y hemos dejado un montón
de la memoria en nuestra estela.

196
00:09:33,636 --> 00:09:35,260
Y eso es lo que los cuadrados grises son.

197
00:09:35,260 --> 00:09:40,540
Y probablemente se sentía como que tuvo un
mucho más tiempo que la ordenación por inserción, burbuja

198
00:09:40,540 --> 00:09:42,660
especie, o la selección de clasificación.

199
00:09:42,660 --> 00:09:45,330
>> Pero, en realidad, ya que un
Muchos de estos procesos

200
00:09:45,330 --> 00:09:48,260
están sucediendo al mismo tiempo--
que es algo que voy a hacer, de nuevo,

201
00:09:48,260 --> 00:09:51,100
hablar cuando hablamos de
recursividad en un futuro video--

202
00:09:51,100 --> 00:09:53,799
este algoritmo en realidad
claramente es fundamentalmente

203
00:09:53,799 --> 00:09:55,590
diferente a cualquier cosa
hemos visto antes

204
00:09:55,590 --> 00:09:58,820
pero también es significativamente
mas eficiente.

205
00:09:58,820 --> 00:09:59,532
>> ¿Porque es eso?

206
00:09:59,532 --> 00:10:01,240
Bueno, en el peor de los casos
de los casos, tenemos

207
00:10:01,240 --> 00:10:04,830
dividir n elementos arriba
y luego recombinar ellos.

208
00:10:04,830 --> 00:10:06,680
Pero cuando recombinarlo
ellos, lo que estamos haciendo

209
00:10:06,680 --> 00:10:11,110
es, básicamente, la duplicación de la
tamaño de las matrices más pequeñas.

210
00:10:11,110 --> 00:10:14,260
Tenemos un montón de un elemento
arrays que efectivamente

211
00:10:14,260 --> 00:10:16,290
combinar en dos conjuntos de elementos.

212
00:10:16,290 --> 00:10:18,590
Y luego tomamos los
dos conjuntos de elementos

213
00:10:18,590 --> 00:10:21,890
y combinarlos en
cuatro conjuntos de elementos, y así sucesivamente,

214
00:10:21,890 --> 00:10:26,130
y así sucesivamente, y así sucesivamente, hasta que
tener una sola n elemento de la matriz.

215
00:10:26,130 --> 00:10:29,910
>> Pero, ¿cuántos duplicaciones
Qué se necesita para llegar al n?

216
00:10:29,910 --> 00:10:31,460
Piense de nuevo al ejemplo de la guía telefónica.

217
00:10:31,460 --> 00:10:34,490
¿Cuántas veces tenemos que romper
la guía telefónica en medio, ¿cuántos más

218
00:10:34,490 --> 00:10:38,370
veces tenemos que romper la guía telefónica
a la mitad, si el tamaño de la guía telefónica

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

220
00:10:39,680 --> 00:10:41,960
Sólo hay una, ¿no?

221
00:10:41,960 --> 00:10:45,360
>> Así que hay algún tipo de
elemento logarítmica aquí.

222
00:10:45,360 --> 00:10:48,590
Pero también queda por lo menos
mirar a todos los n elementos.

223
00:10:48,590 --> 00:10:53,860
Así que en el peor de los casos,
ordenamiento por mezcla corre n log n.

224
00:10:53,860 --> 00:10:56,160
Tenemos que mirar
todos los elementos N,

225
00:10:56,160 --> 00:11:02,915
y tenemos que combinarlos
juntos en log n conjuntos de pasos.

226
00:11:02,915 --> 00:11:05,290
En el mejor de los casos,
la matriz está perfectamente ordenadas.

227
00:11:05,290 --> 00:11:06,300
Eso es genial.

228
00:11:06,300 --> 00:11:09,980
Pero basado en el algoritmo que tenemos aquí,
todavía tenemos que dividir y recombinar.

229
00:11:09,980 --> 00:11:13,290
Aunque en este caso, la
recombinación es una especie de ineficaz.

230
00:11:13,290 --> 00:11:14,720
No es necesario.

231
00:11:14,720 --> 00:11:17,580
Pero todavía atravesamos
todo el proceso de todos modos.

232
00:11:17,580 --> 00:11:21,290
>> Así, en el mejor de los casos
y en el peor de los casos,

233
00:11:21,290 --> 00:11:24,970
este algoritmo se ejecuta en n log n tiempo.

234
00:11:24,970 --> 00:11:29,130
Combinar tipo es sin duda un poco más complicado
que los otros algoritmos de clasificación principales

235
00:11:29,130 --> 00:11:33,470
hemos hablado de CS50 pero es
sustancialmente más potente.

236
00:11:33,470 --> 00:11:35,400
>> Y por lo que si alguna vez se encuentra
ocasión para la necesitan

237
00:11:35,400 --> 00:11:38,480
o utilizarlo para ordenar una
gran conjunto de datos, consiguiendo

238
00:11:38,480 --> 00:11:41,940
su cabeza alrededor de la idea de recursividad
va a ser muy poderosa.

239
00:11:41,940 --> 00:11:45,270
Y que va a hacer su
programas realmente mucho más eficiente

240
00:11:45,270 --> 00:11:48,700
utilizando fusionar especie frente nada más.

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

242
00:11:49,640 --> 00:11:51,970
Esto es CS50.

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