Merge Sort
Merge Sort è uno degli algoritmi di ordinamento più veloci. Molte applicazioni utilizzano alcune versioni di Merge Sort in produzione. In precedenza abbiamo analizzato algoritmi con complessità quadratica come Bubble sort o Selection sort. Merge Sort è decisamente più rapido rispetto a tutti gli algoritmi di ordinamento di tipo quadratico e funziona in tempo .
Merge Sort è un algoritmo di tipo divide-and-conquer che ordina ricorsivamente parti dell’array e poi le unisce. Il cuore dell’algoritmo è un metodo efficiente per fondere due array ordinati in un unico array ordinato. Durante la sua elaborazione, Merge Sort divide l’array in due parti, ordina ricorsivamente la prima parte, poi fa lo stesso con la seconda parte e infine unisce i due array ordinati in un solo array:
def merge(a, b):
i, j, res = 0, 0, [] # Indice per a e b e array risultante
while i < len(a) or j < len(b): # Finché ci sono ancora elementi
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] => prendi a[i]
res.append(ai) # Aggiungi a[i] al risultato
i += 1 # Passa all'elemento successivo
else: # Se a[i] >= b[j] => prendi b[j]
res.append(bj) # Aggiungi b[j] al risultato
j += 1 # Passa all'elemento successivo
return res
def merge_sort(a):
if len(a) <= 1: # Nessun elemento da ordinare
return a # Restituisce l'array iniziale
l = merge_sort(a[: len(a) // 2]) # Ordina la parte sinistra
r = merge_sort(a[len(a) // 2:]) # Ordina la parte destra
return merge(l, r)A ogni passo, l’algoritmo prende l’array, lo divide in due parti, le ordina separatamente e poi unisce i risultati in un nuovo array. Nota che tutti gli algoritmi precedentemente trattati modificavano l’array originale in place (cioè senza creare un nuovo array), mentre Merge Sort crea un nuovo array a ogni iterazione. È piuttosto difficile far sì che Merge Sort operi in-place. Riesci a spiegare il perché?
Simuliamo ora l’algoritmo su alcuni array:
[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]
Challenge
Dato un array di
n interi, devi ordinarli in ordine discendente utilizzando l’algoritmo Merge Sort.Input
La prima riga dell’input contiene un singolo intero
n (1 ≤ n ≤ 100 000).La riga successiva contiene
n interi separati da spazi ( ≤ ≤ ) che rappresentano l’array iniziale.Output
Il programma deve stampare
n interi separati da spazi in ordine decrescente.Examples
Input | Output |
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