Merge sort

Estruturas de Dados e Algoritmos em Python

Miriam Antona

Software engineer

Merge sort

Segue o método de dividir e conquistar
- Dividir
  - quebra o problema em subproblemas menores
- Conquistar
  - resolve os subproblemas recursivamente
- Combinar
  - combina as soluções dos subproblemas para obter a solução final

Merge sort - na prática

Representação esquemática de uma lista com números desordenados.

Merge sort - na prática

Representação esquemática de uma lista com números desordenados. A lista foi dividida em duas partes.

Merge sort - na prática

Representação esquemática de uma lista com números desordenados. A lista foi dividida em duas partes. Há duas novas listas: a primeira com a metade esquerda da original e a segunda com a metade direita.

Merge sort - na prática

Representação esquemática de uma lista com números desordenados. As novas listas foram divididas em duas partes.

Merge sort - na prática

Representação esquemática de uma lista com números desordenados. Novas listas mostram divisões das listas já divididas.

Merge sort - na prática

Representação esquemática de uma lista com números desordenados. As novas listas foram divididas em duas partes.

Merge sort - na prática

Representação esquemática de uma lista com números desordenados. Novas listas mostram divisões das últimas listas divididas.

Merge sort - na prática

Representação esquemática de uma lista com números desordenados. As novas listas foram divididas em duas partes.

Merge sort - na prática

Representação esquemática de uma lista com números desordenados. As novas listas foram divididas em duas partes.

Merge sort - na prática

Representação esquemática de uma lista com números desordenados. Os elementos das últimas listas divididas foram ordenados.

Merge sort - na prática

Representação esquemática de uma lista com números desordenados. Os elementos das últimas listas divididas foram mesclados e ordenados.

Merge sort - na prática

Representação esquemática de uma lista com números desordenados. Os elementos das últimas listas divididas foram mesclados e ordenados.

Merge sort - na prática

Representação esquemática de uma lista com números desordenados. Os elementos das últimas listas divididas foram mesclados e ordenados. Todos os elementos estão ordenados.

Merge sort - implementação

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 - complexidade

Pior caso: $O(n\log{}n)$
- melhora muito sobre bubble, selection e insertion sort
- bom para listas grandes
Caso médio: $\Theta(n\log{}n)$
Melhor caso: $\Omega(n\log{}n)$
- outros algoritmos (ex.: bubble, insertion) têm melhor melhor caso
Complexidade de espaço: $O(n)$
- pior que algoritmos com $O(1)$
Há variantes que reduzem esse espaço

Vamos praticar!

Estruturas de Dados e Algoritmos em Python