Come funziona?

Merge Sort segue tre passaggi: dividere, conquistare e combinare.

Procedimento passo dopo passo:

1. Dividere: dividi l'array in due metà.
2. Conquistare: ordina ricorsivamente ciascuna metà. Una parte con un elemento (o nessuno) è già ordinata, quindi la ricorsione si interrompe lì.
3. Combinare: unisci le due metà ordinate in un unico array ordinato.

Esempio su [6, 3, 8, 5]:

• Dividi in [6, 3] e [8, 5]
• Dividi ancora: [6], [3], [8], [5]
• Unisci [6] e [3] in [3, 6]
• Unisci [8] e [5] in [5, 8]
• Unisci [3, 6] e [5, 8] in [3, 5, 6, 8]