Tutorial de Merge Sort em Python

A ordenação de dados é uma das operações mais comuns que os praticantes de dados fazem em seu trabalho diário. Muitas vezes precisamos exibir dados em uma ordem específica 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.

Existem várias estratégias para ordenar dados. Neste tutorial, analisaremos uma das técnicas de ordenação mais eficazes. O algoritmo “merge sort” usa uma estratégia de dividir e conquistar para ordenar um array não ordenado, 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 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 do que o merge sort. Não surpreendentemente, este algoritmo é usado em todos os tipos de aplicações do mundo real, como ordenar grandes bancos de dados ou organizar 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 subproblemas menores. 
• Conquistar: os subproblemas são resolvidos de forma recursiva. 
• Combinar: as soluções dos subproblemas são combinadas para obter a solução final.

Estratégia de dividir e conquistar

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

Problema de Merge Sort. Fonte: DataCamp

Complexidade de Tempo e Espaço do Merge Sort

É impossível saber de antemão 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 em que são executados e as particularidades dos dados a serem ordenados.

Embora não possamos prever o tempo exato de execução 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ção Big O e Complexidade de Tempo, o objetivo da análise de complexidade de tempo não é prever o tempo exato de execução de um algoritmo, mas sim avaliar o quão eficiente um algoritmo é, analisando como o 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, notada 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á.

Devido ao fato de a complexidade de tempo do merge sort se comportar 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

Por fim, além do tempo necessário para concluir a tarefa, outro aspecto importante ao analisar a complexidade de algoritmos é estimar quanto de 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. O ú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 usado pela entrada.

A ordenação por mesclagem tem uma complexidade de espaço de O(N). Isso ocorre porque utiliza um array auxiliar de tamanho N para mesclar as metades ordenadas do array de entrada. O array auxiliar é utilizado para armazenar o resultado mesclado, e o array de entrada é sobrescrito com o resultado ordenado.

Implementação da Ordenação por Mesclagem em Python

Vamos implementar o algoritmo de ordenação por mesclagem em Python. Existem 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 ordenação por mesclagem

Se você é novo no assunto, em programação, a recursão acontece quando uma função chama a si mesma. Você pode conferir nosso Entendendo Funções Recursivas em Python Tutorial 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 os elementos de ambas as metades. Se o elemento atual em left_half for menor, o colocamos em my_list[k] e movemos i para frente. Caso contrário, pegamos o elemento de right_half, o 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 toda a lista 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 usado 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

O merge sort tem um alto desempenho ao classificar listas grandes, mas sua eficiência diminui ao trabalhar com listas menores. Igualmente, tende a ser menos eficiente em cenários onde já existe algum grau de ordem nas listas de entrada, pois o merge sort executará as mesmas etapas, não importando a ordem da lista.

Um ótimo caso de uso em que o merge sort é particularmente útil são as listas encadeadas. Uma lista encadeada é uma estrutura de dados que compreende uma conexão de nós ligados linearmente entre si. Cada nó contém os dados e o link para conectá-lo ao próximo nó.

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

Erros Comuns e Solução de Problemas

O algoritmo merge sort é 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 o merge sort 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 o insertion sort, podem funcionar melhor. Nesse caso, você só precisaria criar um limite de tamanho abaixo do qual você optaria pelo algoritmo insertion sort em vez de merge sort.

Além disso, uma boa ideia para explorar seria a paralelização. Os passos do merge sort podem ser facilmente paralelizados com a potência computacional certa, reduzindo assim o tempo de conclusão. Leia nosso guia Processador vs GPU para aprender 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 crescente universo dos algoritmos. Se você tem interesse nas especificidades dos algoritmos, como funcionam e suas complexidades, virtudes e desvantagens associadas, esses recursos do DataCamp podem ajudá-lo 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 de Analista de Dados em Python
• Notação Big O e Complexidade de Tempo