Guida pratica al merge sort (con esempi pratici)

Il merge sort è stato ideato da John von Neumann negli anni ’40. Tuttavia, il concetto di merge sort è stato formalizzato e pubblicato per la prima volta da John von Neumann e da un collega, Herman Goldstine, nel 1945 nel documento intitolato “Planning and Coding of Problems for an Electronic Computing Instrument”.

Perchè è utile

Questo algoritmo di ordinamento è noto per la sua efficienza e per il suo approccio divide et impera, che lo rende una delle scelte popolari per l’ordinamento di grandi quantità di dati.

Implementazione in Python dell’algoritmo merge sort

# Python program for implementation of MergeSort


def mergeSort(arr):
	if len(arr) > 1:

		# Finding the mid of the array
		mid = len(arr)//2

		# Dividing the array elements
		L = arr[:mid]

		# Into 2 halves
		R = arr[mid:]

		# Sorting the first half
		mergeSort(L)

		# Sorting the second half
		mergeSort(R)

		i = j = k = 0

		# Copy data to temp arrays L[] and R[]
		while i < len(L) and j < len(R):
			if L[i] <= R[j]:
				arr[k] = L[i]
				i += 1
			else:
				arr[k] = R[j]
				j += 1
			k += 1

		# Checking if any element was left
		while i < len(L):
			arr[k] = L[i]
			i += 1
			k += 1

		while j < len(R):
			arr[k] = R[j]
			j += 1
			k += 1


# Code to print the list
def printList(arr):
	for i in range(len(arr)):
		print(arr[i], end=" ")
	print()


# Driver Code
if __name__ == '__main__':
	arr = [12, 11, 13, 5, 6, 7]
	print("Given array is")
	printList(arr)
	mergeSort(arr)
	print("\nSorted array is ")
	printList(arr)

# This code is contributed by Mayank Khanna
# source: https://www.geeksforgeeks.org/merge-sort/

In cosa consiste

Il merge sort è un algoritmo di ordinamento basato sull’approccio “divide et impera”, che suddivide ricorsivamente un’array in sottoproblemi più piccoli, li ordina e poi combina le soluzioni dei sottoproblemi per ottenere l’array ordinato. Ecco una descrizione generale del funzionamento del merge sort:

1. Divide: L’array non ordinato viene diviso a metà in modo ricorsivo fino a quando non si ottengono singoli elementi o sottoproblemi di dimensione 1.
2. Conquista: Una volta che gli elementi sono divisi in singoli elementi (considerati ordinati per definizione), l’algoritmo inizia a combinare gli elementi in modo ordinato. Questo processo di fusione avviene combinando due sottoparti ordinate per creare una parte ordinata più grande. Questo passaggio è chiamato “merge”.
3. Merge: L’operazione di merge prende due sottoparti ordinate e le fonde in un’unica parte ordinata. Questo viene fatto confrontando gli elementi più piccoli di entrambe le sottoparti e posizionando il più piccolo nell’array ordinato risultante. L’operazione di merge continua fino a quando tutti gli elementi delle sottoparti non sono stati inseriti nell’array ordinato.
4. Ricombina: Questo processo di divisione e fusione continua fino a quando tutte le sottoparti non sono state unite in un’unica parte ordinata, creando così l’array completamente ordinato.

L’implementazione pratica di merge sort coinvolge tipicamente una funzione ricorsiva che divide l’array in due parti, ordina le due parti separatamente e infine fonde le due parti ordinate in un’unica parte ordinata.

Analisi della complessità del merge sort