Agora direcionamos nossa atenção para usar uma estratégia de divisão e conquistar como uma maneira de melhorar o desempenho dos algoritmos de ordenação. O primeiro algoritmo que estudamos é misturar misturando. A ordem de mistura é um algoritmo recursivo que divide continuamente uma lista ao meio. Se a lista estiver vazia ou tiver um único item, ele será encomendado por definição (a caixa Base). Se a lista tiver mais de um item, dividimos a lista e insinuando novamente uma ordem de mistura para ambas as metades. Uma vez que as duas metades são ordenadas, a operação fundamental é realizada, chamada de mistura. A mistura é o processo de tirar duas listas ordenadas menores e combiná-las em uma única lista nova e ordenada. A Figura 10 mostra nossa lista de exemplo de família, pois está sendo dividido por ordenamientoPorMezcla. A Figura 11 mostra as listas simples, agora ordenadas, pois se fundam novamente.

a função ordenamientoPorMezcla Mostrado no ActiveCode 1 começa pedindo a caixa de base. Se a duração da lista for menor ou igual a uma, então já temos uma lista ordenada e não é necessário mais processamento. Se, por outro lado, o comprimento for maior que um, então usamos a operação slice de Python para extrair as metades esquerda e direita. É importante ter em mente que a lista pode não ter um par de itens. Isso não importa, uma vez que os comprimentos serão diferentes no máximo em um.

Uma vez que a função na metade esquerda e à direita ( Linhas 8-9), presume-se que eles são encomendados. O restante da função (linhas 11-31) é responsável por mixar as duas listas ordenadas menores em uma lista ordenada maior. Observe que a operação de mistura localiza os itens novamente na lista original (unaLista) Um de cada vez, retirando repetidamente o mínimo das listas ordenadas.

a função ordenamientoPorMezcla foi aumentado com uma instrução print (linha 2) para mostrar o conteúdo da lista que está sendo encomendada no início de cada invocação Há também uma instrução print (linha 32) para mostrar o processo de mistura. A impressão mostra o resultado da execução da função com nossa lista de exemplo. Observe que a lista com itens 44, 55 e 20 não será dividida em partes iguais. A primeira divisão dá e no segundo dia. É fácil de ver como o processo de divisão ocasionalmente produz uma lista que pode ser misturada imediatamente com outras listas ordenadas.

Analisar a função ordenamientoPorMezcla Devemos considerar os dois processos diferentes que compõem sua implementação. Primeiro, a lista é dividida em metades. Nós já somos calculados (em uma busca binária) que podemos dividir uma lista ao meio em um tempo \ (\ log n \) onde n é o comprimento da lista. O segundo processo é a mistura. Cada item da lista será processado e colocado na lista ordenada. Portanto, a operação de mistura que resulta em uma lista de n exige n operações. O resultado dessa análise é que eles são feitos \ (\ log n \) divisões, cada uma das quais custa \ (n \) para um total de operações \ (n \ log n \). Uma ordem de mistura é um algoritmo \ (ou (n \ log n) \).

Lembre-se que o operador da partição é \ (ou (k) \) onde k é o tamanho da partição. Para garantir que ordenamientoPorMezcla seja \ (ou (n \ log n) \) teremos que remover o operador da partição. Mais uma vez, isso é possível se simplesmente passarmos os índices iniciais e finais junto com a lista quando fizermos a chamada recursiva. Deixamos isso como um exercício.

É importante notar que a função ordenamientoPorMezcla requer espaço adicional para armazenar as duas metades como elas são extraídas com operações de partição. Esse espaço adicional pode ser um fator crítico se a lista for grande e puder ser problemática para este pedido ao trabalhar em grandes conjuntos de dados.