A classificação é tradicionalmente uma tarefa difícil em ciência da computação . A escolha de um algoritmo de ordenação que é eficiente e rápida pode ser difícil . Muitas vezes, eficiente escolha algoritmo envolve o conhecimento dos dados a serem ordenados , e os tipos especializados costumam funcionar muito melhor do que generalizada algoritmos de ordenação . No entanto, certos tipos , como o " merge sort ", pode trabalhar em situações generalizadas por quebrar conjuntos e triagem pequenos pedaços de forma recursiva. A Lista

Um merge sort é um " dividir e conquistar" algoritmo, em que é preciso porções das listas e continuamente quebra-los em metades até atingir elementos únicos da lista , que depois são incorporadas em ordem. Por exemplo, começar com uma lista numérica como

5 6 2 4 1 9 8 3 7

Classificando uma lista como esta com um merge sort exigirá reduzir pela metade repetidamente o tamanho da lista até que cada número básico existe sozinho. Em seguida, a espécie pode comparar os números e colocá-los juntos na ordem correta ( menor para o maior , neste caso).
O método Merge

O método merge é simples:

def merge ( primeira, segunda )

Levando duas listas , o método irá fundi-las , começando no início de cada lista. Em seguida, ele acrescenta o seguinte valor mínimo de cada lista em uma nova lista . O resultado é uma lista ordenada . ( Lembre-se de inserir corretamente guia espaço em branco após as declarações ", enquanto " e " if /else" . ) :

Enquanto i < len (primeiro) e j < len ( segundo) :

se primeiro [i] < = segundo [j] :

new_list.append ( primeiro [i])

i = i + 1

mais:

new_list.append ( segundo [j] )

j = j + 1 }

Finalmente, depois de uma lista termina , os valores restantes são colocados na nova lista :

new_list + = primeiro [i : ]

new_list + = segundo [j ]:

retornar end_list
merge sort Condições

a mesclagem real leva tipo do algoritmo de classificação principal. Existem duas principais partes funcionais : o aspecto condicional que pára a recursão uma vez que as listas são subdivididos ea recursão real que metades das listas. A condição de parada vem em primeiro lugar :

def mergesort (lista) :

if len (lista) == 1 :

retornar lista

Isso garante que quando uma lista de sub atinge apenas um elemento , esse elemento é retornado para que ele a ser mesclado com outros números.
Merge Sort recursão

a segunda metade do o tipo é a recursão. Após a instrução "if" /condicional , como segue:

mais:

middle = len ( lista ) /2

start = mergesort (lista [ meio : ] )

end = mergesort (lista [: média ] )

merge retorno ( início, fim)

Devido a recursão, após as listas são divididas em elementos únicos , o algoritmo volta rastreia até o último método executado. Então , no momento em que a declaração " merge retorno ( início, fim) " executa , o algoritmo retorna um mesclado, lista de dois mescladas anteriormente , classificado listas de tamanho menor classificada.