Tutorial do Python Merge Sort

A classificação de dados é uma das operações mais comuns que os profissionais de dados fazem em seu trabalho diário. Muitas vezes, precisamos exibir os dados em uma determinada ordem para extrair informações significativas. Felizmente, hoje em dia não precisamos fazer essa tarefa manualmente. Os computadores podem fazer a mágica para nós com um desempenho imbatível.

Há várias estratégias para classificar os dados. Neste tutorial, analisaremos uma das técnicas de classificação mais eficazes. O algoritmo "merge sort" usa uma estratégia de dividir e conquistar para classificar um array não classificado, primeiro dividindo-o em arrays menores, que são posteriormente mesclados na ordem correta. 

Nas próximas seções, discutiremos todos os detalhes do algoritmo de classificação de mesclagem, sua aparência em Python e algumas dicas práticas para uma implementação tranquila.

O que é Merge Sort?

Há muitos algoritmos de classificação disponíveis, mas é difícil encontrar um que tenha um desempenho melhor do que o merge sort. Não é de surpreender que esse algoritmo seja usado em todos os tipos de aplicativos do mundo real, como a classificação de grandes bancos de dados ou a organização de arquivos em um computador comum.

O algoritmo é baseado no paradigma dividir e conquistar, que pode ser dividido em três partes:

• Dividir: esse processo divide o problema em subproblemas menores. 
• Conquistar: os subproblemas são resolvidos de forma recursiva. 
• Combinar: as soluções dos subproblemas são combinadas para que você obtenha a solução final.

Estratégia de dividir e conquistar

Vamos ver como funciona a classificação por mesclagem. Suponha que você queira ordenar os números a seguir aplicando o algoritmo de classificação por mesclagem. O algoritmo divide os dados recursivamente em duas partes e continua dividindo até que cada lista tenha um elemento. Em seguida, nós as combinamos, classificando-as em outra lista.

Problema de classificação de mesclagem. Fonte: DataCamp

Complexidade de tempo e espaço da classificação de mesclagem

É impossível saber com antecedência qual é o algoritmo de classificação que funciona melhor para um determinado problema. Diversas variáveis precisam ser consideradas além do algoritmo, incluindo a linguagem de programação usada para escrever o código, o hardware no qual ele é executado e as particularidades dos dados a serem classificados. 

Embora não possamos prever o tempo exato de execução de um algoritmo de classificação, ainda podemos comparar o desempenho de vários algoritmos de classificação analisando a complexidade de tempo e espaço.

Complexidade de tempo da classificação de mesclagem

Como explicamos em um guia separado sobre Notação Big O e complexidade de tempo, o objetivo da análise de complexidade de tempo não é prever o tempo de execução exato de um algoritmo, mas sim avaliar a eficiência de um algoritmo analisando como seu tempo de execução muda à medida que a quantidade de dados de entrada aumenta.

A análise de complexidade de tempo é escrita na notação Big O, uma notação matemática que descreve a taxa na qual uma função cresce ou diminui. A classificação de mesclagem tem uma complexidade de tempo log-linear ou linearítmica, conhecida como O(N log(N)), em que N é o número de elementos na lista. A letra "O" representa a "ordem" de crescimento. 

Na análise de complexidade de tempo, a complexidade linearítmica se comporta de forma aproximadamente semelhante à complexidade linear, o que significa que sua execução será diretamente proporcional à quantidade de dados. Portanto, se a quantidade de dados dobrar, o tempo que o algoritmo leva para processar os dados também deverá dobrar, ou seja, o número de divisões e mesclagens dobrará.

Como a complexidade de tempo da classificação de mesclagem se comporta linearmente, sua complexidade permanece a mesma para os casos melhor, médio e pior. Isso significa que, independentemente da ordem de entrada, o algoritmo sempre levará o mesmo número de etapas para ser concluído.

Complexidade espacial da classificação de mesclagem

Por fim, além do tempo necessário para concluir a tarefa, outro aspecto importante ao analisar a complexidade do algoritmo é estimar a quantidade de memória que o algoritmo exigirá para ser concluído à medida que o problema se torna maior. 

Isso é coberto pelos conceitos de complexidade espacial e espaço auxiliar. O último refere-se ao espaço extra ou espaço temporário usado por um algoritmo, enquanto o primeiro refere-se ao espaço total ocupado pelo algoritmo em relação ao tamanho da entrada. Em outras palavras, a complexidade do espaço inclui tanto o espaço auxiliar quanto o espaço usado pela entrada.

A classificação de mesclagem tem uma complexidade de espaço de O(N). Isso ocorre porque ele usa uma matriz auxiliar de tamanho N para mesclar as metades classificadas da matriz de entrada. A matriz auxiliar é usada para armazenar o resultado mesclado, e a matriz de entrada é substituída pelo resultado classificado.

Implementação do Merge Sort em Python

Vamos implementar o algoritmo de classificação de mesclagem em Python. Há várias maneiras de codificar o algoritmo; no entanto, vamos nos ater àquela baseada em recursão, que é, sem dúvida, a mais fácil de entender e requer menos linhas de código do que outras alternativas baseadas em iteração.

Entendendo a recursão na classificação de mesclagem

Se você ainda não conhece o assunto, em programação, a recursão ocorre quando uma função chama a si mesma. Você pode conferir nosso tutorial Entendendo funções recursivas em Python para saber tudo sobre essas poderosas funções.

Para implementar a classificação por mesclagem, primeiro definimos o caso básico: se a lista tiver apenas um elemento, ela já estará classificada e, portanto, retornaremos imediatamente. Caso contrário, dividimos a lista em duas metades, left_half e right_half, e chamamos merge_sort() recursivamente em cada uma delas. Esse processo continua até que todas as sublistas contenham um único elemento.

Quando tivermos essas sublistas classificadas, começaremos o processo de mesclagem. Para fazer isso, inicializamos três variáveis de índice: i para rastrear a posição em left_half, j para right_half e k para a lista final mesclada. Em seguida, comparamos os elementos das duas metades. Se o elemento atual em left_half for menor, você o colocará em my_list[k] e avançará em i. Caso contrário, pegamos o elemento de right_half, o colocamos em my_list[k] e incrementamos j. Após cada comparação, avançamos k para a próxima posição na lista final.

Esse processo continua até que tenhamos comparado todos os elementos em uma das metades. Se algum elemento permanecer em left_half ou right_half, nós o anexaremos diretamente à lista final, garantindo que nenhum dado seja deixado para trás. Como a classificação por mesclagem opera de forma recursiva, esse processo de mesclagem é executado em todos os níveis de recursão até que toda a lista seja classificada.

Implementação do Python

Abaixo, você pode encontrar o código usando a lista não classificada do diagrama anterior como exemplo:

def merge_sort(my_list):
    if len(my_list) > 1: 
        mid = len(my_list)//2
        left_half = my_list[:mid]
        right_half = my_list[mid:]
       
        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0
 
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                my_list[k] = left_half[i]                
                i += 1
            else:
                my_list[k] = right_half[j]
                j += 1
            k += 1
     
        while i < len(left_half):
            my_list[k] = left_half[i]
            i += 1
            k += 1
 
        while j < len(right_half):
            my_list[k] = right_half[j]
            j += 1
            k += 1

my_list = [35,22,90,4,50,20,30,40,1]
merge_sort(my_list)
print(my_list)
>>> [1, 4, 20, 22, 30, 35, 40, 50, 90]

Merge Sort versus outros algoritmos de classificação

O Merge Sort é um algoritmo de classificação bastante rápido, especialmente adequado para grandes bancos de dados, e é frequentemente usado como referência para outros algoritmos. No entanto, quando se trata de listas mais curtas, seu desempenho tende a ser inferior ao de outros algoritmos de classificação.

Na tabela a seguir, você pode encontrar uma comparação do merge sort com outros algoritmos de classificação populares.

Aplicações práticas do Merge Sort

A classificação por mesclagem tem um alto desempenho ao classificar listas grandes, mas sua eficiência diminui ao trabalhar com listas menores. Da mesma forma, ele tende a ser menos eficiente em cenários em que já existe algum grau ou ordem nas listas de entrada, pois a classificação por mesclagem executará as mesmas etapas, independentemente da ordem da lista.

Um ótimo caso de uso em que a classificação por mesclagem é particularmente útil são as listas vinculadas. Uma lista vinculada é uma estrutura de dados que compreende uma conexão de nós linearmente vinculados uns aos outros. Cada nó contém os dados e o link para conectá-lo ao próximo nó.

A classificação por mesclagem é preferível para listas vinculadas porque requer apenas acesso sequencial aos dados, o que se alinha bem à natureza das listas vinculadas. Além disso, a classificação por mesclagem é um algoritmo de classificação estável (ou seja, preserva a ordem relativa de elementos iguais na saída classificada), o que é uma consideração muito importante para manter a ordem das listas vinculadas.

Erros comuns e solução de problemas

O algoritmo de classificação de mesclagem é bastante simples, e o espaço para aprimoramento do código é limitado. No entanto, você pode aumentar a complexidade da sua estratégia de classificação levando em conta o tamanho dos dados de entrada. 

Já estabelecemos que a classificação por mesclagem funciona melhor com conjuntos de dados maiores. Para conjuntos de dados menores, outros algoritmos de classificação com complexidade de tempo O(N^2), como a classificação por inserção, funcionam melhor. Nesse caso, você só precisaria criar um limite de tamanho abaixo do qual optaria pelo algoritmo de classificação de inserção em vez de mesclar e classificar.

Além disso, uma boa ideia a ser explorada seria a paralelização. As etapas da classificação de mesclagem podem ser facilmente paralelizadas com o poder de computação adequado, reduzindo assim o tempo de conclusão. Leia nosso guia CPU vs GPU para saber mais sobre computação paralela. 

Conclusão

A classificação por mesclagem é um dos algoritmos de classificação mais eficazes e populares que existem, mas há muito mais a aprender no maravilhoso e sempre crescente universo dos algoritmos. Se você se interessa pelos aspectos técnicos dos algoritmos, como eles funcionam e a complexidade, as virtudes e as desvantagens associadas a eles, esses recursos do DataCamp podem ajudá-lo a continuar seu aprendizado:

• Curso de Introdução a Estruturas de Dados e Algoritmos 
• Trilha de habilidades de programação Python
• Pista de habilidades de fundamentos de dados Python
• Curso de Python Intermediário
• Analista de dados em Python Trilha de carreira 
• Notação Big O e complexidade de tempo