Algoritmo di ordinamento Merge sort in JavaScript

Merge sort è un efficace algoritmo di ordinamento basato sul principio "divide et impera". Questo metodo suddivide ricorsivamente l'array in sotto-array più piccoli, li ordina singolarmente e poi combina i sotto-array ordinati per ottenere l'array ordinato finale. Esploriamo in dettaglio il funzionamento e l'implementazione di merge sort in JavaScript.

L'algoritmo merge sort utilizza il concetto di "divide et impera" per ordinare un array. Il processo di ordinamento coinvolge i seguenti passaggi:

1. Dividi: l'array viene diviso a metà ricorsivamente finché ogni sotto-array contiene uno o nessun elemento.

2. Conquista: gli elementi dei sotto-array vengono ordinati singolarmente.

3. Combina: i sotto-array ordinati vengono combinati gradualmente in un'unica sequenza ordinata, fondendo i sotto-array in modo che l'array risultante sia ordinato.

Implementazione di merge sort in JavaScript

Ecco un'implementazione di base di merge sort in JavaScript:

function mergeSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  const middle = Math.floor(arr.length / 2);
  const left = arr.slice(0, middle);
  const right = arr.slice(middle);

  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  let result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

Questo codice definisce una funzione mergeSort che accetta un array come argomento e lo ordina utilizzando l'algoritmo merge sort.

let array = [64, 34, 25, 12, 22, 11, 90];
console.log(mergeSort(array)); // Output: [11, 12, 22, 25, 34, 64, 90]

Complessità temporale di merge sort

Merge sort ha una complessità temporale garantita di O(n log n) in tutti i casi, rendendolo un algoritmo efficiente per grandi dataset. Questo lo rende una scelta popolare in molte situazioni pratiche.

Merge sort è ampiamente utilizzato in applicazioni reali a causa della sua efficienza su grandi dataset. Tuttavia, richiede più spazio in memoria per memorizzare i sotto-array durante l'ordinamento. È particolarmente vantaggioso su dataset collegati o su dati distribuiti.