Tutorial de Merge Sort em Python

Ordenar dados é uma das operações mais comuns que os profissionais de dados realizam em seu trabalho diário. Muitas vezes, precisamos exibir 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 por nós com um desempenho imbatível.

Existem várias estratégias para ordenar dados. Neste tutorial, vamos analisar uma das técnicas de ordenação mais eficazes. O algoritmo “merge sort” utiliza uma estratégia de dividir e conquistar para ordenar uma matriz não ordenada, primeiro dividindo-a em matrizes menores, que são posteriormente mescladas na ordem correta. 

Nas próximas seções, discutiremos todos os detalhes do algoritmo merge sort, como ele é implementado em Python e algumas dicas práticas para uma implementação tranquila.

O que é Merge Sort?

Existem muitos algoritmos de ordenação por aí, mas é difícil encontrar um que tenha um desempenho melhor que o merge sort. Não é surpresa que esse algoritmo seja usado em todos os tipos de aplicações do mundo real, como a ordenação de grandes bancos de dados ou a organização de arquivos em um computador comum.

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

• Dividir: este processo divide o problema em sub-problemas menores. 
• Conquistar: os sub-problemas são resolvidos de forma recursiva. 
• Combinar: as soluções dos sub-problemas são combinadas para alcançar a solução final.

Estratégia de dividir e conquistar

Vamos ver como o merge sort funciona. Suponhamos que queremos ordenar os seguintes números aplicando o algoritmo de merge sort. O algoritmo divide os dados de forma recursiva em duas partes e continua dividindo até que cada lista tenha um elemento. Em seguida, combinamos eles ordenando-os em outra lista.

Problema de Merge Sort. Fonte: DataCamp

Complexidade de Tempo e Espaço do Merge Sort

É impossível saber antecipadamente qual é o algoritmo de ordenação que funciona melhor para um determinado problema. Várias 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 eles são executados e as particularidades dos dados a serem ordenados. 

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

Complexidade de Tempo do merge sort

Como explicamos em um guia separado sobre Notaçao 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 quão eficiente é um algoritmo ao analisar como seu tempo de execução muda conforme a quantidade de dados de entrada aumenta.

A análise de complexidade de tempo é escrita em notação Big O, uma notação matemática que descreve a taxa na qual uma função cresce ou decresce. O merge sort tem complexidade de tempo log-linear ou linearítmica, indicada como O(N log(N)), onde 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 aproximadamente de forma semelhante à complexidade linear, o que significa que sua execução será diretamente proporcional à quantidade de dados. Assim, se a quantidade de dados for dobrada, o tempo que o algoritmo leva para processar os dados também deve dobrar, ou seja, o número de divisões e mesclagens dobrará.

Porque a complexidade de tempo do merge sort se comporta de forma linear, sua complexidade permanece a mesma para os melhores, médios e piores casos. Isso significa que, independentemente da ordem de entrada, o algoritmo sempre levará o mesmo número de passos para ser concluído.

Complexidade de espaço do merge sort

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

Isso é coberto pelos conceitos de complexidade de espaço e espaço auxiliar. Este último refere-se ao espaço extra ou espaço temporário utilizado 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 de espaço inclui tanto o espaço auxiliar quanto o espaço utilizado pela entrada.

O merge sort tem uma complexidade de espaço de O(N). Isso ocorre porque ele utiliza uma matriz auxiliar de tamanho N para mesclar as metades ordenadas da matriz de entrada. A matriz auxiliar é usada para armazenar o resultado mesclado, e a matriz de entrada é sobrescrita com o resultado ordenado.

Implementação do Merge Sort em Python

Vamos implementar o algoritmo merge sort em Python. Existem várias maneiras de codificar o algoritmo; no entanto, vamos nos ater à baseada em recursão, que é provavelmente a mais fácil de entender e requer menos linhas de código do que outras alternativas baseadas em iteração.

Compreendendo a recursão no merge sort

Se você é novo no assunto, na programação, a recursão acontece quando uma função chama a si mesma. Você pode conferir nosso Tutorial sobre Funções Recursivas em Python para aprender tudo sobre essas funções poderosas.

Para implementar o merge sort, primeiro definimos o caso base: se a lista tiver apenas um elemento, ela já está ordenada, então retornamos 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.

Uma vez que temos essas sublistas ordenadas, começamos 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 mesclada final. Em seguida, comparamos elementos de ambas as metades. Se o elemento atual em left_half for menor, colocamos em my_list[k] e movemos i para a frente. Caso contrário, pegamos o elemento de right_half, colocamos em my_list[k] e incrementamos j. Após cada comparação, movemos k para a próxima posição na lista final.

Esse processo continua até que tenhamos comparado todos os elementos de uma das metades. Se restarem elementos em left_half ou right_half, os anexamos diretamente à lista final, garantindo que nenhum dado seja deixado para trás. Como o merge sort opera de forma recursiva, esse processo de mesclagem é executado em cada nível de recursão até que a lista inteira esteja ordenada.

Implementação em Python

Abaixo, você pode encontrar o código usando a lista não ordenada 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 vs Outros Algoritmos de Ordenação

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

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

Aplicações práticas do Merge Sort

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

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

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

Erros Comuns e Solução de Problemas

O algoritmo de classificação por mistura é bastante direto, e o espaço para melhorias no código é limitado. No entanto, você pode aumentar a complexidade de sua estratégia de classificação levando em consideração o tamanho dos dados de entrada.

Já estabelecemos que a classificação por mistura 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, podem funcionar melhor. Nesse caso, você só precisaria criar um limite de tamanho abaixo do qual optaria pelo algoritmo de classificação por inserção em vez de classificar e mesclar.

Para além disso, uma boa ideia a explorar seria a paralelização. Os passos do merge sort podem ser facilmente paralelizados com a potência computacional adequada, reduzindo assim o tempo de conclusão. Leia nosso guia Processador vs GPU para saber mais sobre computação paralela.

Conclusão

O merge sort é um dos algoritmos de ordenação mais eficazes e populares, mas há muito mais a aprender no maravilhoso e sempre em expansão universo dos algoritmos. Se estiver interessado nas especificidades dos algoritmos, como funcionam e suas complexidades, virtudes e desvantagens associadas, esses recursos do DataCamp podem ajudar você a continuar sua aprendizagem:

• Curso de Introdução a Estruturas de Dados e Algoritmos
• Trilha de Habilidades em Programação Python
• Trilha de Fundamentos de Dados em Python
• Curso Intermediário de Python
• Trilha de Carreira Analista de Dados em Python
• Notação Big O e Complexidade de Tempo