Merge Sort

Introduzione

Merge Sort è il primo algoritmo di ordinamento di questa serie che utilizza la ricorsione.

L’idea chiave è:

1. Divide: spezza l’array a metà, poi spezza le metà a loro volta, finché non ottieni array di un solo elemento (che sono per definizione già ordinati)
2. Conquer (merge): combina due array già ordinati in un array più grande ordinato

All’inizio sembra inefficiente “rompere tutto” in array di un solo elemento, ma in realtà Merge Sort è uno degli algoritmi di sorting più efficienti che possiamo scrivere per dati generici:

• Time complexity: O(n × log n)
• Space complexity aggiuntiva: O(n)

Funzione helper: merge di due array ordinati

Idea intuitiva

Prima di scrivere Merge Sort, serve una funzione helper merge che prenda due array già ordinati e li combini in un unico array ordinato:

• teniamo due indici:
  • i per il primo array
  • j per il secondo array
• finché entrambi gli array hanno elementi:
  • confrontiamo arr1[i] e arr2[j]
  • il valore più piccolo viene pushato nel nuovo array combined
  • incrementiamo l’indice (i o j) dell’array da cui abbiamo preso l’elemento
• quando uno dei due array finisce:
  • pushiamo in blocco tutti gli elementi rimanenti dell’altro array

Implementazione di merge

1
// Funzione helper che unisce due array ORDINATI in un unico array ORDINATO
2
function merge(arr1, arr2) {
3
  // Nuovo array che conterrà tutti gli elementi ordinati
4
  const combined = [];
5

6
  // Indici per scandire i due array di input
7
  let i = 0; // indice per arr1
8
  let j = 0; // indice per arr2
9

10
  // Finché entrambi gli array hanno ancora elementi da confrontare
11
  while (i < arr1.length && j < arr2.length) {
12
    // Confronta l'elemento corrente di arr1 con quello di arr2
13
    if (arr1[i] < arr2[j]) {
14
      // Se arr1[i] è più piccolo, lo aggiungiamo al risultato
15
      combined.push(arr1[i]);
16
      // e passiamo all'elemento successivo di arr1
17
      i++;
18
    } else {
19
      // Altrimenti arr2[j] è più piccolo o uguale
20
      combined.push(arr2[j]);
21
      // e passiamo all'elemento successivo di arr2
22
      j++;
23
    }
24
  }
25

26
  // A questo punto almeno uno dei due array è esaurito.
27
  // Se in arr1 sono rimasti elementi, li aggiungiamo tutti in coda.
28
  while (i < arr1.length) {
29
    combined.push(arr1[i]);
30
    i++;
31
  }
32

33
  // Se in arr2 sono rimasti elementi, li aggiungiamo tutti in coda.
34
  while (j < arr2.length) {
35
    combined.push(arr2[j]);
36
    j++;
37
  }
38

39
  // Ritorniamo il nuovo array ordinato
40
  return combined;
41
}

Questa funzione segue esattamente la logica introdotta nella sezione precedente:

• usa due indici (i e j)
• confronta sempre il più piccolo tra i due
• quando un array finisce, scarica tutto il resto dell’altro

Complessità di merge:

• Time: O(n + m) dove n e m sono le lunghezze dei due array
• Space: O(n + m) per il nuovo array combined

Implementazione di Merge Sort (ricorsivo)

Struttura generale

Merge Sort esegue sempre gli stessi due passi ricorsivi:

1. Base case: se l’array ha lunghezza 1, è già ordinato → lo ritorniamo così com’è
2. Caso ricorsivo:
   • calcoliamo un midpoint con Math.floor(array.length / 2)
   • creiamo due nuovi array:
     • left = array.slice(0, midIndex)
     • right = array.slice(midIndex)
   • chiamiamo ricorsivamente mergeSort(left) e mergeSort(right)
   • combiniamo i due risultati usando la funzione merge

Importante: Merge Sort non ordina l’array in-place.
Ritorna un nuovo array ordinato, lasciando intatto l’array originale.

Codice di Merge Sort

1
// Merge Sort: ordina un array usando la strategia "divide and conquer"
2
function mergeSort(array) {
3
  // BASE CASE:
4
  // Un array con un solo elemento è già ordinato → lo ritorniamo direttamente.
5
  if (array.length === 1) {
6
    return array;
7
  }
8

9
  // Calcoliamo l'indice centrale spezzando l'array a metà.
10
  // Usiamo Math.floor per gestire correttamente anche lunghezze dispari.
11
  const midIndex = Math.floor(array.length / 2);
12

13
  // Creiamo il sotto-array di sinistra usando slice:
14
  // parte dall'indice 0 e arriva fino (ma NON incluso) a midIndex.
15
  const left = array.slice(0, midIndex);
16

17
  // Creiamo il sotto-array di destra:
18
  // parte da midIndex e va fino alla fine dell'array.
19
  const right = array.slice(midIndex);
20

21
  // Chiamate ricorsive:
22
  // - ordiniamo ricorsivamente il sotto-array di sinistra
23
  // - ordiniamo ricorsivamente il sotto-array di destra
24
  const sortedLeft = mergeSort(left);
25
  const sortedRight = mergeSort(right);
26

27
  // Combiniamo i due sotto-array ORDINATI usando la funzione helper merge.
28
  // Il risultato è un nuovo array ordinato che contiene tutti gli elementi.
29
  return merge(sortedLeft, sortedRight);
30
}

Comportamento su un esempio

Con un array [4, 2, 6, 1]:

1. mergeSort([4, 2, 6, 1])
   • left = [4, 2], right = [6, 1]
2. mergeSort([4, 2]) → diventa [4] e [2] → merge([4], [2]) → [2, 4]
3. mergeSort([6, 1]) → diventa [6] e [1] → merge([6], [1]) → [1, 6]
4. merge([2, 4], [1, 6]) → [1, 2, 4, 6]

L’array originale rimane [4, 2, 6, 1]; il risultato ordinato è il nuovo array ritornato da mergeSort.

Big O di Merge Sort

Space Complexity – O(n)

Per ordinare un array di n elementi:

• abbiamo l’array originale
• durante il processo creiamo:
  • array left
  • array right
  • array combinati dei vari livelli

In totale, lo spazio aggiuntivo usato per rappresentare gli elementi durante le fasi di split/merge è proporzionale a n:

• Space complexity: O(n)

Time Complexity – O(n × log n)

Merge Sort ha due componenti principali:

• Split (divide):
  • ad ogni livello dividiamo l’array a metà
  • numero di livelli ≈ (\log_2(n)) (es. con 8 elementi servono 3 “tagli”: (2^3 = 8))
• Merge (conquer):
  • ad ogni livello, la somma degli elementi che stiamo mergeando è sempre n
  • il lavoro per livello è quindi O(n) (grazie alla funzione merge)

Combinando:

• livelli ≈ log n
• lavoro per livello ≈ n

Otteniamo:

• Time complexity: O(n × log n)

In pratica, per array grandi, Merge Sort è molto più efficiente degli algoritmi O(n²) (Bubble, Selection, Insertion Sort).

Esercizio: Merge di due Linked List ordinate (interview question)

Descrizione del problema

Abbiamo una classe LinkedList singly linked, con:

• this.head: nodo iniziale
• this.tail: nodo finale
• this.length: numero di nodi nella lista

Vogliamo implementare un metodo:

• merge(otherList)
  che unisce la lista corrente con otherList, assumendo che:
  • entrambe le liste siano già ordinate in ordine crescente
  • i nodi siano riutilizzati (non creiamo nuovi nodi, solo ricolleghiamo i next)

Alla fine:

• la lista corrente (this) conterrà tutti gli elementi ordinati
• otherList sarà “consumata” (i suoi nodi vengono agganciati alla lista corrente)

Esempio:

1
// l1: 1 -> 3 -> 5 -> 7
2
const l1 = new LinkedList(1);
3
l1.push(3);
4
l1.push(5);
5
l1.push(7);
6

7
// l2: 2 -> 4 -> 6 -> 8
8
const l2 = new LinkedList(2);
9
l2.push(4);
10
l2.push(6);
11
l2.push(8);
12

13
// Dopo il merge:
14
// l1: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8
15
l1.merge(l2);

Idea (stessa logica di merge sugli array)

Il pattern è identico al merge tra due array ordinati, ma invece di usare indici su un array:

• usiamo puntatori a nodi:
  • this.head per la lista corrente
  • otherHead per l’altra lista
• usiamo un nodo fittizio (dummy) come testa temporanea della lista fusa
• current tiene traccia dell’ultimo nodo inserito nella lista risultante

Passi:

1. Confronta this.head.value con otherHead.value
2. Collega il nodo con valore più piccolo a current.next
3. Avanza nella lista da cui hai preso il nodo (this.head = this.head.next oppure otherHead = otherHead.next)
4. Avanza current (current = current.next)
5. Quando una delle due liste finisce, collega in coda tutti i nodi rimasti dell’altra
6. Imposta this.head = dummy.next (saltiamo il nodo fittizio)
7. Aggiorna this.tail (se necessario) e this.length

Implementazione di merge per LinkedList

1
// Metodo di istanza della classe LinkedList
2
// Unisce la lista corrente (this) con un'altra lista otherList,
3
// assumendo che entrambe siano già ordinate in modo crescente.
4
merge(otherList) {
5
  // Puntatore alla testa della lista da unire
6
  let otherHead = otherList.head;
7

8
  // Nodo "fittizio" che ci aiuta a costruire facilmente la lista fusa
9
  let dummy = { value: 0, next: null };
10

11
  // 'current' punterà sempre all'ultimo nodo della lista fusa
12
  let current = dummy;
13

14
  // Finché entrambe le liste hanno ancora nodi
15
  while (this.head !== null && otherHead !== null) {
16
    // Confrontiamo il valore in testa alle due liste
17
    if (this.head.value < otherHead.value) {
18
      // Il nodo della lista corrente è più piccolo:
19
      // lo colleghiamo in coda alla lista fusa
20
      current.next = this.head;
21
      // Avanziamo la testa della lista corrente
22
      this.head = this.head.next;
23
    } else {
24
      // Il nodo della otherList è più piccolo:
25
      // lo colleghiamo in coda alla lista fusa
26
      current.next = otherHead;
27
      // Avanziamo la testa della otherList
28
      otherHead = otherHead.next;
29
    }
30

31
    // Avanziamo il puntatore 'current' al nuovo ultimo nodo
32
    current = current.next;
33
  }
34

35
  // A questo punto almeno una delle due liste è finita.
36
  // Se nella lista corrente ci sono ancora nodi, li colleghiamo in coda.
37
  if (this.head !== null) {
38
    current.next = this.head;
39
  } else {
40
    // Altrimenti colleghiamo tutti i nodi rimasti di otherList
41
    current.next = otherHead;
42
    // Se abbiamo attaccato nodi di otherList in coda,
43
    // la tail della lista risultante deve diventare la tail di otherList
44
    this.tail = otherList.tail;
45
  }
46

47
  // La nuova testa della lista fusa è il nodo successivo al dummy
48
  this.head = dummy.next;
49

50
  // Aggiorniamo la lunghezza: somma delle due liste
51
  this.length += otherList.length;
52
}

Complessità del merge tra due LinkedList

• Time complexity: O(n + m)
  • ogni nodo di entrambe le liste viene visitato al massimo una volta
• Space complexity aggiuntiva: O(1)
  • non creiamo nuovi nodi, riusiamo quelli esistenti e un solo nodo fittizio in stack

Questo esercizio è un’ottima variante “da colloquio” del concetto di merge:

• la logica è la stessa del merge sugli array
• cambia solo la struttura dati (liste collegate invece di array)