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.

Conclusione

Merge Sort è un algoritmo efficiente di ordinamento che utilizza una strategia "divide et impera". La sua complessità temporale garantita di O(n log n) lo rende un'ottima scelta per ordinare grandi quantità di dati.