Merge Sort
O Merge sort é um dos algoritmos de ordenação mais rápidos. Muitas aplicações utilizam algumas variações do Merge sort em produção. Já falámos de algoritmos que funcionam em tempo quadrático , como o Bubble sort ou o Selection sort. O Merge sort é bem mais rápido do que todos os algoritmos quadráticos de ordenação, pois funciona em tempo .
O Merge sort é um algoritmo do tipo “divide e conquista” (divide-and-conquer) que ordena partes do array de forma recursiva e as combina posteriormente. O ponto central do algoritmo é a forma eficiente de fundir dois arrays ordenados num só array ordenado. Durante a execução, o algoritmo divide o array em duas partes. Em seguida, ordena recursivamente a primeira parte. Depois, ordena recursivamente a segunda parte. Por último, funde esses dois arrays ordenados num único array ordenado:
def merge(a, b):
i, j, res = 0, 0, [] # Índice para a e b, com o array resultante
while i < len(a) or j < len(b): # Enquanto ainda houver elementos
ai = a[i] if i < len(a) else float('inf')
bj = b[j] if j < len(b) else float('inf')
if ai < bj: # Se a[i] < b[j], então usar a[i]
res.append(ai) # Adicionar a[i] ao resultado
i += 1 # Avançar para o próximo elemento
else: # Se a[i] >= b[j], então usar b[j]
res.append(bj) # Adicionar b[j] ao resultado
j += 1 # Avançar para o próximo elemento
return res
def merge_sort(a):
if len(a) <= 1: # Nada para ordenar
return a # Retornar o array inicial
l = merge_sort(a[: len(a) // 2]) # Ordenar a parte esquerda
r = merge_sort(a[len(a) // 2:]) # Ordenar a parte direita
return merge(l, r)Em cada etapa, o algoritmo pega no array, divide-o em duas partes, ordena cada uma separadamente e combina os resultados num novo array. Nota que todos os algoritmos anteriores discutidos modificavam o array original in place (isto é, faziam as alterações sem criar um novo array), enquanto o Merge sort cria um novo array em cada iteração. É bastante difícil fazer com que o Merge sort trabalhe in place. Consegues explicar porquê?
Vamos simular o algoritmo em vários arrays:
[4, 1, -1, 0, 2, 8]
merge_sort([4, 1, -1, 0, 2, 8]):merge_sort([4, 1, -1])merge_sort([0, 2, 8])
merge_sort([4, 1, -1])merge_sort([4])→ return[4]merge_sort([1, -1])
merge_sort([0, 2, 8])merge_sort([1])→ return[1]merge_sort([-1])→ return[-1]
merge_sort([4, 1, -1]):
merge_sort([4])→ return[4]
merge_sort([1, -1])merge_sort([0])→ return[0]merge_sort([2, 8])
merge_sort([1, -1]):merge_sort([2])→ return[2]merge_sort([8])→ return[8]
merge_sort([1])→ return[1]
merge_sort([-1])→ return[-1]
- Back to
merge_sort([1, -1])→ return[-1, 1]
Desafio
Dado um array de
n inteiros, a tarefa consiste em ordená-los em ordem decrescente utilizando o algoritmo Merge Sort.Entrada
A primeira linha da entrada contém um único inteiro
n (1 ≤ n ≤ 100 000).A linha seguinte contém
n inteiros separados por espaços ( ≤ ≤ ) representando o array inicial.Saída
O programa deve imprimir
n inteiros separados por espaço em ordem decrescente.Exemplos
Entrada | Saída |
4
7 4 9 1 | 9 7 4 1 |
5
-4 8 2 -3 6 | 8 6 2 -3 -4 |
Constraints
Time limit: 5 seconds
Memory limit: 512 MB
Output limit: 10 MB