[Música tocando] 

DOUG LLOYD: OK, então uma mesclagem tipo é mais um algoritmo que podemos usar para resolver os elementos de uma matriz. Mas, como veremos, tem um diferença muito fundamental de seleção tipo, bolha tipo e ordenação por inserção que o tornam realmente muito inteligente. 

A idéia básica por trás de mesclagem tipo é classificar matrizes menores e, em seguida, combinar essas matrizes juntos, ou mesclar eles-- daí o nome-- na ordem de classificação. A maneira que merge sort faz isto é, aproveitando uma ferramenta chamado recursão, que é o que nós vamos estar falando em breve, mas nós realmente não conversamos sobre isso ainda. 

Aqui é a idéia básica por trás merge sort. Classificar a metade esquerda da matriz, assumindo que n é maior do que 1. E o que eu quero dizer quando digo assumindo que n é maior do que 1 é, Eu acho que nós podemos concordar que se uma matriz consiste somente de um único elemento, ele é classificado. Nós realmente não precisa para fazer qualquer coisa para ele. Podemos apenas declará-lo para ser classificado. É apenas um único elemento. 

Assim, o pseudocódigo, novamente, é ordenar a metade do lado esquerdo da matriz, em seguida, classificar a metade direita da matriz, em seguida, mesclar as duas metades juntas. Agora, já que você pode ser pensando, ele tipo de apenas Parece que você está adiando as-- você não está realmente fazendo alguma coisa. Você está dizendo classificar à esquerda metade, ordenar a metade direita, mas você não está dizendo me como você está fazendo isso. 

Mas lembre-se que, enquanto uma matriz é um único elemento, podemos declará-la classificada. Então nós podemos apenas combiná-los juntos. E isso é realmente o ideia fundamental por trás merge sort, é para quebrá-lo para baixo, de modo que suas matrizes são de tamanho um. E então você reconstruir a partir daí. 

Merge sort é definitivamente um algoritmo complicado. E é também um pouco complicada para visualizar. Portanto, esperamos que, a visualização que eu temos aqui vai ajudá-lo a seguir adiante. E eu vou tentar o meu melhor para narrar as coisas e prosseguir com este um pouco mais lentamente do que os outros apenas com a esperança de obter a sua cabeça em torno das idéias por trás merge sort. 

Portanto, temos a mesma matriz como a outras algoritmo de classificação vídeos se você já viu eles-- uma matriz de seis elementos. E o nosso código pseudocode aqui é classificar a metade esquerda, ordenar a metade direita, mesclar as duas metades juntas. Então, vamos dar este tijolo vermelho muito escuro array e classificar a metade esquerda do mesmo. 

Então, por enquanto, vamos a ignorar as coisas à direita. É lá, mas estamos não naquele passo ainda. Nós não somos a espécie a metade direita da matriz. Estamos em espécie à esquerda metade da matriz. E apenas por uma questão de ser um pouco mais claro, para que eu possa consultar para o passo que estamos no, Eu vou mudar o cor deste conjunto de laranja. Agora, nós ainda estamos falando sobre o mesma metade esquerda da matriz original. Mas eu estou esperando que por ser capaz de referem-se às cores de vários itens, ele vai torná-lo um pouco mais claro o que está acontecendo aqui. 

OK, então agora temos um três matriz elemento. Como podemos classificar a metade esquerda deste matriz, o que é ainda neste passo? Nós estamos tentando classificar a esquerda metade do tijolo vermelho array-- a metade esquerda das quais Eu tenho agora de cor laranja. 

Bem, nós poderíamos tentar repetir esse processo novamente. Então, nós ainda estamos no meio tentando classificar a metade esquerda da matriz completa. A metade esquerda do array, eu só vou para decidir arbitrariamente que a metade esquerda será menor do que a metade direita, porque isto acontece a composto por três elementos. 

E assim eu vou dizer que o metade esquerda da metade esquerda da matriz é apenas o elemento cinco. Cinco, sendo um único elemento array, nós sabemos como resolver isso. E assim cinco está classificada. Nós apenas estamos indo para declarar isso. É uma única matriz elemento. 

Então, nós temos agora classificados o metade esquerda da esquerda half-- ou melhor, temos classificados o metade esquerda da laranja. Então, agora, a fim de ainda completa metade esquerda da matriz total, precisamos classificar a metade direita da laranja, ou essas coisas. Como fazemos isso? Bem, nós temos um array com dois elementos. Assim, podemos classificar a metade esquerda da matriz, que é dois. Dois é um único elemento. Por isso é classificado por padrão. Então, podemos classificar a metade direita de que a porção de matriz, a uma. Isso é tipo de por padrão. 

Isto é agora pela primeira vez chegamos a um passo de mesclagem. Nós completamos, embora agora estamos tipo de aninhados down-- e que é uma espécie de complicado coisa com recursividade é, você precisa para manter seu cabeça sobre onde nós estamos. Então, nós tipo de esquerda metade da porção de laranja. 

E agora, nós estamos no meio de triagem a metade direita da porção de laranja. E, nesse processo, estamos agora prestes a ser no degrau, mesclar as duas metades juntas. Quando olhamos para as duas metades da matriz, vemos dois e um. Elemento que é menor? Uma. 

Em seguida, o qual elemento é menor? Bem, é duas ou nada. Portanto, é dois. Então, agora, só para enquadrar novamente onde estamos no contexto, nós ter resolvido o metade esquerda da laranja e a metade direita da origem. Eu sei que eu mudei as cores de novo, mas que é onde estávamos. E a razão pela qual eu fiz isso é porque este processo é vai continuar, a iteração para baixo. Temos classificados esquerda a metade da laranja ex e a metade direita do ex-laranja. 

Agora, precisamos mesclar aqueles duas metades juntos também. Essa é a etapa em que estamos. Portanto, considerar todas as elementos que são agora verde, a metade esquerda da matriz original. E nós mesclar aqueles utilizando o mesmo processo de fizemos para mesclar dois e um apenas um momento atrás. 

A metade da esquerda, a menor elemento na metade esquerda é cinco. O elemento mais pequeno a metade direita é um deles. Qual dessas é menor? Uma. 

O elemento mais pequeno a metade esquerda é cinco. O elemento mais pequeno a metade direita é dois. Qual é o menor? Dois. E por último, em seguida, cinco e nada, podemos dizer cinco. 

OK, portanto, grande figura, vamos fazer uma pausa por um segundo e descobrir onde estamos. Se começássemos a partir de o início, nós agora completou para a matriz global apenas um passo do código pseudocode aqui. Nós ter resolvido o metade esquerda da matriz. 

Lembre-se que o original ordem era cinco, dois, um. Ao passar por este processo e nidificação para baixo e repetir, continuando a quebrar o problema em partes cada vez menores, temos agora concluída um passo do pseudocode para toda a matriz de partida. Nós ter resolvido sua meia esquerda. 

Então agora vamos congelar lá. E agora vamos classificar a direita metade da matriz original. E vamos fazer isso por passando pela mesma iterativo processo de quebrar as coisas e, em seguida, mesclando-los juntos. 

Assim, a metade esquerda da vermelho, ou a metade esquerda da metade direita do original array, eu vou dizer é três. Mais uma vez, eu estou sendo consistente aqui. Se você tem um estranho número de elementos, ela Não importa realmente se você faz o esquerdo menor ou o direito de um menor. 

O que importa é que sempre que você deparar com este problema na condução uma mala, você precisa ser consistente. Você quer sempre precisa fazer um lado esquerdo menor ou sempre precisa fazer o lado direito menor. Aqui, eu escolhi para sempre fazer o lado esquerdo menor quando minha matriz, ou o meu sub-array, é de uma dimensão ímpar. 

Três é um único elemento, e por isso é ordenada. Temos aproveitado essa suposição em todo o nosso processo até agora. Então agora vamos classificar a direita metade da metade direita, ou a metade direita do vermelho. 

Mais uma vez, temos de dividir isso para baixo. Este não é um único elemento de matriz. Não podemos declará-la classificada. E assim em primeiro lugar, vamos para classificar a metade esquerda. 

A metade da esquerda é um único elemento, por isso é tipo de por padrão. Então vamos classificar a direita metade, que é um único elemento. É classificado por padrão. E agora, que pode mesclar os dois juntos. Quatro é menor, e em seguida, seis é menor. 

Mais uma vez, o que temos feito neste momento? Temos classificados esquerda metade da metade direita. Ou voltar para o original cores que estavam lá, temos ordenados esquerda metade do vermelho mais suave. Ele foi originalmente um tijolo escuro vermelho e agora é um vermelho mais suave, ou um vermelho foi mais suave. 

E então temos o classificado metade direita do vermelho mais suave. Agora, bem, eles são verde novamente, apenas porque estamos passando por um processo. E nós temos que repetir isso mais e mais. 

Então agora podemos mesclar aqueles duas metades juntas. E isso é o que fazemos aqui. Assim, a linha preta apenas dividido a metade esquerda ea metade direita da parte tipo. 

Nós comparamos o menor valor no lado esquerdo da array-- ou me desculpar, o menor valor da metade esquerda para o valor menor da direita metade e descobrir que três é menor. E agora um pouco de uma otimização, certo? Há realmente nada esquerda, no lado esquerdo. 

Não há nada restante do lado esquerdo, para que possamos eficientemente apenas move-- podemos declarar o resto é, na verdade, classificadas e apenas pregá-la sobre, porque não há nada outra para comparação. E nós sabemos que o lado direito do lado direito está classificada. 

OK, então agora vamos congelar novamente e descobrir onde estamos na história. Em geral a matriz, o que temos feito? Nós realmente realizar Agora as etapas um e dois etapa. Separamos a metade esquerda, e nós ordenamos a metade direita. 

Então, agora, tudo o que resta é para nós para mesclar essas duas metades juntas. Então, nós comparamos o menor valorizado elemento de cada metade da matriz por sua vez, e prossiga. Um é inferior a três, para que se passa. 

Dois é inferior a três, assim que dois vai. Três é inferior a 5, de modo que três tentativas. Quatro é inferior a 5, de modo que vai de quatro. Em seguida, cinco é menos de seis, e seis é tudo o que resta. 

Agora, eu sei, isso foi uma série de etapas. E nós deixamos muito de memória em nossa esteira. E é isso que esses são quadrados cinza. E provavelmente me senti como que teve um muito mais do que a ordenação por inserção, bolha sort, ou ordenação por seleção. 

Mas, na realidade, porque um muitos destes processos estão acontecendo ao mesmo tempo-- que é algo que vai, mais uma vez, falar quando falamos de recursão em um futuro video-- este algoritmo efectivamente claramente é fundamentalmente diferente de tudo temos visto antes mas também é significativamente mais eficiente. 

Por que é que? Bem, na pior cenário, temos para dividir n elementos up e em seguida recombinam-los. Mas quando nós recombinar los, o que estamos fazendo é basicamente dobrando o tamanho das matrizes menores. Temos um monte de um elemento matrizes que efectivamente combinar em duas matrizes de elementos. E, em seguida, tomamos aqueles duas matrizes elemento e combiná-los em quatro matrizes de elementos, e assim por diante, e assim por diante, e assim por diante, até que tem uma única matriz elemento n. 

Mas quantas duplicações que é preciso para chegar ao n? Pense de volta para o exemplo do livro de telefone. Quantas vezes temos de rasgar o livro de telefone pela metade, quantos mais vezes temos de rasgar o livro de telefone em metade, se o tamanho do livro de telefone duplicou? Há apenas um, certo? 

Portanto, há algum tipo de elemento logarítmica aqui. Mas nós também ainda temos que, pelo menos, olhar para todos os n elementos. Assim, no pior dos casos, merge sort é executado em log n n. Temos de olhar para todos os n elementos, e nós temos que combiná-los em conjunto em N log N conjuntos de passos. Na melhor das hipóteses, a matriz é perfeitamente ordenadas. Isso é ótimo. Mas baseado no algoritmo que temos aqui, ainda temos de dividir e recombinar. Embora, neste caso, o recombinação é uma espécie de ineficaz. Isto não é necessário. Mas nós ainda passar por todo o processo de qualquer maneira. 

Assim, na melhor das hipóteses e, no pior caso, este algoritmo é executado em log n n tempo. Merge sort é definitivamente um pouco mais complicado do que os outros principais algoritmos de ordenação nós já conversamos sobre CS50, mas é substancialmente mais poderoso. 

E por isso, se você alguma vez encontrar- ocasião para precisar dele ou usá-lo para classificar uma grande conjunto de dados, obtendo sua cabeça em torno da idéia de recursão vai ser realmente poderoso. E ele vai fazer o seu programas realmente muito mais eficiente usando merge sort contra qualquer outra coisa. Eu sou Doug Lloyd. Este é CS50.