logo

TechCodeview

Merge Sort – Tutorial sulla struttura dei dati e sugli algoritmi

Unisci ordinamento è un algoritmo di ordinamento che segue il dividere e conquistare approccio. Funziona dividendo ricorsivamente l'array di input in sottoarray più piccoli e ordinando tali sottoarray, quindi unendoli nuovamente insieme per ottenere l'array ordinato.

In termini semplici, possiamo dire che il processo di unisci ordinamento consiste nel dividere l'array in due metà, ordinare ciascuna metà e quindi unire nuovamente le metà ordinate. Questo processo viene ripetuto finché l'intero array non viene ordinato.

Algoritmo di ordinamento-unione-(1)

Unisci algoritmo di ordinamento



Come funziona l'ordinamento unito?

Merge sort è un algoritmo di ordinamento popolare noto per la sua efficienza e stabilità. Ne consegue il dividere e conquistare approccio per ordinare un dato array di elementi.

Ecco una spiegazione passo passo di come funziona l'ordinamento mediante unione:

  1. Dividere: Dividi l'elenco o l'array ricorsivamente in due metà finché non può più essere diviso.
  2. Conquistare: Ogni sottoarray viene ordinato individualmente utilizzando l'algoritmo di ordinamento di unione.
  3. Unisci: I sottoarray ordinati vengono riuniti insieme in ordine ordinato. Il processo continua finché tutti gli elementi di entrambi i sottoarray non sono stati uniti.

Illustrazione dell'ordinamento di unione:

Ordiniamo l'array o l'elenco [38, 27, 43, 10] utilizzando l'ordinamento unito

Diamo un’occhiata al funzionamento dell’esempio sopra:

Dividere:

  • [38, 27, 43, 10] è diviso in [38, 27 ] E [43, 10] .
  • [38, 27] è diviso in [38] E [27] .
  • [43, 10] è diviso in [43] E [10] .

Conquistare:

  • [38] è già ordinato.
  • [27] è già ordinato.
  • [43] è già ordinato.
  • [10] è già ordinato.

Unisci:

  • Unisci [38] E [27] ottenere [27, 38] .
  • Unisci [43] E [10] ottenere [10:43] .
  • Unisci [27, 38] E [10:43] per ottenere l'elenco ordinato finale [10, 27, 38, 43]

Pertanto, l'elenco ordinato è [10, 27, 38, 43] .

Pratica consigliata Provalo!

Implementazione di Merge Sort:

C++ 
// C++ program for Merge Sort #include  using namespace std; // Merges two subarrays of array[]. // First subarray is arr[begin..mid] // Second subarray is arr[mid+1..end] void merge(int array[], int const left, int const mid,  int const right) {  int const subArrayOne = mid - left + 1;  int const subArrayTwo = right - mid;  // Create temp arrays  auto *leftArray = new int[subArrayOne],  *rightArray = new int[subArrayTwo];  // Copy data to temp arrays leftArray[] and rightArray[]  for (auto i = 0; i < subArrayOne; i++)  leftArray[i] = array[left + i];  for (auto j = 0; j < subArrayTwo; j++)  rightArray[j] = array[mid + 1 + j];  auto indexOfSubArrayOne = 0, indexOfSubArrayTwo = 0;  int indexOfMergedArray = left;  // Merge the temp arrays back into array[left..right]  while (indexOfSubArrayOne < subArrayOne  && indexOfSubArrayTwo < subArrayTwo) {  if (leftArray[indexOfSubArrayOne]  <= rightArray[indexOfSubArrayTwo]) {  array[indexOfMergedArray]  = leftArray[indexOfSubArrayOne];  indexOfSubArrayOne++;  }  else {  array[indexOfMergedArray]  = rightArray[indexOfSubArrayTwo];  indexOfSubArrayTwo++;  }  indexOfMergedArray++;  }  // Copy the remaining elements of  // left[], if there are any  while (indexOfSubArrayOne < subArrayOne) {  array[indexOfMergedArray]  = leftArray[indexOfSubArrayOne];  indexOfSubArrayOne++;  indexOfMergedArray++;  }  // Copy the remaining elements of  // right[], if there are any  while (indexOfSubArrayTwo < subArrayTwo) {  array[indexOfMergedArray]  = rightArray[indexOfSubArrayTwo];  indexOfSubArrayTwo++;  indexOfMergedArray++;  }  delete[] leftArray;  delete[] rightArray; } // begin is for left index and end is right index // of the sub-array of arr to be sorted void mergeSort(int array[], int const begin, int const end) {  if (begin>= fine) ritorno;  int mid = inizio + (fine - inizio) / 2;  mergeSort(array, inizio, metà);  mergeSort(array, metà + 1, fine);  merge(array, inizio, metà, fine); } // FUNZIONI DI UTILITÀ // Funzione per stampare un array void printArray(int A[], int size) { for (int i = 0; i< size; i++)  cout << A[i] << ' ';  cout << endl; } // Driver code int main() {  int arr[] = { 12, 11, 13, 5, 6, 7 };  int arr_size = sizeof(arr) / sizeof(arr[0]);  cout << 'Given array is 
';  printArray(arr, arr_size);  mergeSort(arr, 0, arr_size - 1);  cout << '
Sorted array is 
';  printArray(arr, arr_size);  return 0; } // This code is contributed by Mayank Tyagi // This code was revised by Joshua Estes>
C 
// C program for Merge Sort #include  #include  // Merges two subarrays of arr[]. // First subarray is arr[l..m] // Second subarray is arr[m+1..r] void merge(int arr[], int l, int m, int r) {  int i, j, k;  int n1 = m - l + 1;  int n2 = r - m;  // Create temp arrays  int L[n1], R[n2];  // Copy data to temp arrays L[] and R[]  for (i = 0; i < n1; i++)  L[i] = arr[l + i];  for (j = 0; j < n2; j++)  R[j] = arr[m + 1 + j];  // Merge the temp arrays back into arr[l..r  i = 0;  j = 0;  k = l;  while (i < n1 && j < n2) {  if (L[i] <= R[j]) {  arr[k] = L[i];  i++;  }  else {  arr[k] = R[j];  j++;  }  k++;  }  // Copy the remaining elements of L[],  // if there are any  while (i < n1) {  arr[k] = L[i];  i++;  k++;  }  // Copy the remaining elements of R[],  // if there are any  while (j < n2) {  arr[k] = R[j];  j++;  k++;  } } // l is for left index and r is right index of the // sub-array of arr to be sorted void mergeSort(int arr[], int l, int r) {  if (l < r) {  int m = l + (r - l) / 2;  // Sort first and second halves  mergeSort(arr, l, m);  mergeSort(arr, m + 1, r);  merge(arr, l, m, r);  } } // Function to print an array void printArray(int A[], int size) {  int i;  for (i = 0; i < size; i++)  printf('%d ', A[i]);  printf('
'); } // Driver code int main() {  int arr[] = { 12, 11, 13, 5, 6, 7 };  int arr_size = sizeof(arr) / sizeof(arr[0]);  printf('Given array is 
');  printArray(arr, arr_size);  mergeSort(arr, 0, arr_size - 1);  printf('
Sorted array is 
');  printArray(arr, arr_size);  return 0; }>
Giava 
// Java program for Merge Sort import java.io.*; class MergeSort {  // Merges two subarrays of arr[].  // First subarray is arr[l..m]  // Second subarray is arr[m+1..r]  void merge(int arr[], int l, int m, int r)  {  // Find sizes of two subarrays to be merged  int n1 = m - l + 1;  int n2 = r - m;  // Create temp arrays  int L[] = new int[n1];  int R[] = new int[n2];  // Copy data to temp arrays  for (int i = 0; i < n1; ++i)  L[i] = arr[l + i];  for (int j = 0; j < n2; ++j)  R[j] = arr[m + 1 + j];  // Merge the temp arrays  // Initial indices of first and second subarrays  int i = 0, j = 0;  // Initial index of merged subarray array  int k = l;  while (i < n1 && j < n2) {  if (L[i] <= R[j]) {  arr[k] = L[i];  i++;  }  else {  arr[k] = R[j];  j++;  }  k++;  }  // Copy remaining elements of L[] if any  while (i < n1) {  arr[k] = L[i];  i++;  k++;  }  // Copy remaining elements of R[] if any  while (j < n2) {  arr[k] = R[j];  j++;  k++;  }  }  // Main function that sorts arr[l..r] using  // merge()  void sort(int arr[], int l, int r)  {  if (l < r) {  // Find the middle point  int m = l + (r - l) / 2;  // Sort first and second halves  sort(arr, l, m);  sort(arr, m + 1, r);  // Merge the sorted halves  merge(arr, l, m, r);  }  }  // A utility function to print array of size n  static void printArray(int arr[])  {  int n = arr.length;  for (int i = 0; i < n; ++i)  System.out.print(arr[i] + ' ');  System.out.println();  }  // Driver code  public static void main(String args[])  {  int arr[] = { 12, 11, 13, 5, 6, 7 };  System.out.println('Given array is');  printArray(arr);  MergeSort ob = new MergeSort();  ob.sort(arr, 0, arr.length - 1);  System.out.println('
Sorted array is');  printArray(arr);  } } /* This code is contributed by Rajat Mishra */>
Pitone 
# Merges two subarrays of array[]. # First subarray is arr[left..mid] # Second subarray is arr[mid+1..right] def merge(array, left, mid, right): subArrayOne = mid - left + 1 subArrayTwo = right - mid # Create temp arrays leftArray = [0] * subArrayOne rightArray = [0] * subArrayTwo # Copy data to temp arrays leftArray[] and rightArray[] for i in range(subArrayOne): leftArray[i] = array[left + i] for j in range(subArrayTwo): rightArray[j] = array[mid + 1 + j] indexOfSubArrayOne = 0 # Initial index of first sub-array indexOfSubArrayTwo = 0 # Initial index of second sub-array indexOfMergedArray = left # Initial index of merged array # Merge the temp arrays back into array[left..right] while indexOfSubArrayOne < subArrayOne and indexOfSubArrayTwo < subArrayTwo: if leftArray[indexOfSubArrayOne] <= rightArray[indexOfSubArrayTwo]: array[indexOfMergedArray] = leftArray[indexOfSubArrayOne] indexOfSubArrayOne += 1 else: array[indexOfMergedArray] = rightArray[indexOfSubArrayTwo] indexOfSubArrayTwo += 1 indexOfMergedArray += 1 # Copy the remaining elements of left[], if any while indexOfSubArrayOne < subArrayOne: array[indexOfMergedArray] = leftArray[indexOfSubArrayOne] indexOfSubArrayOne += 1 indexOfMergedArray += 1 # Copy the remaining elements of right[], if any while indexOfSubArrayTwo < subArrayTwo: array[indexOfMergedArray] = rightArray[indexOfSubArrayTwo] indexOfSubArrayTwo += 1 indexOfMergedArray += 1 # begin is for left index and end is right index # of the sub-array of arr to be sorted def mergeSort(array, begin, end): if begin>= fine: return mid = inizio + (fine - inizio) // 2 mergeSort(array, inizio, metà) mergeSort(array, metà + 1, fine) merge(array, inizio, metà, fine) # Funzione per stampare un array def printArray(array, dimensione): for i in range(dimensione): print(array[i], end=' ') print() # Codice driver if __name__ == '__main__': arr = [12 , 11, 13, 5, 6, 7] arr_size = len(arr) print('L'array indicato è') printArray(arr, arr_size) mergeSort(arr, 0, arr_size - 1) print('
Arr ordinato è') printArray(arr, arr_size)>
C# 
// C# program for Merge Sort using System; class MergeSort {  // Merges two subarrays of []arr.  // First subarray is arr[l..m]  // Second subarray is arr[m+1..r]  void merge(int[] arr, int l, int m, int r)  {  // Find sizes of two  // subarrays to be merged  int n1 = m - l + 1;  int n2 = r - m;  // Create temp arrays  int[] L = new int[n1];  int[] R = new int[n2];  int i, j;  // Copy data to temp arrays  for (i = 0; i < n1; ++i)  L[i] = arr[l + i];  for (j = 0; j < n2; ++j)  R[j] = arr[m + 1 + j];  // Merge the temp arrays  // Initial indexes of first  // and second subarrays  i = 0;  j = 0;  // Initial index of merged  // subarray array  int k = l;  while (i < n1 && j < n2) {  if (L[i] <= R[j]) {  arr[k] = L[i];  i++;  }  else {  arr[k] = R[j];  j++;  }  k++;  }  // Copy remaining elements  // of L[] if any  while (i < n1) {  arr[k] = L[i];  i++;  k++;  }  // Copy remaining elements  // of R[] if any  while (j < n2) {  arr[k] = R[j];  j++;  k++;  }  }  // Main function that  // sorts arr[l..r] using  // merge()  void sort(int[] arr, int l, int r)  {  if (l < r) {  // Find the middle point  int m = l + (r - l) / 2;  // Sort first and second halves  sort(arr, l, m);  sort(arr, m + 1, r);  // Merge the sorted halves  merge(arr, l, m, r);  }  }  // A utility function to  // print array of size n  static void printArray(int[] arr)  {  int n = arr.Length;  for (int i = 0; i < n; ++i)  Console.Write(arr[i] + ' ');  Console.WriteLine();  }  // Driver code  public static void Main(String[] args)  {  int[] arr = { 12, 11, 13, 5, 6, 7 };  Console.WriteLine('Given array is');  printArray(arr);  MergeSort ob = new MergeSort();  ob.sort(arr, 0, arr.Length - 1);  Console.WriteLine('
Sorted array is');  printArray(arr);  } } // This code is contributed by Princi Singh>
Javascript 
// JavaScript program for Merge Sort // Merges two subarrays of arr[]. // First subarray is arr[l..m] // Second subarray is arr[m+1..r] function merge(arr, l, m, r) {  var n1 = m - l + 1;  var n2 = r - m;  // Create temp arrays  var L = new Array(n1);   var R = new Array(n2);  // Copy data to temp arrays L[] and R[]  for (var i = 0; i < n1; i++)  L[i] = arr[l + i];  for (var j = 0; j < n2; j++)  R[j] = arr[m + 1 + j];  // Merge the temp arrays back into arr[l..r]  // Initial index of first subarray  var i = 0;  // Initial index of second subarray  var j = 0;  // Initial index of merged subarray  var k = l;  while (i < n1 && j < n2) {  if (L[i] <= R[j]) {  arr[k] = L[i];  i++;  }  else {  arr[k] = R[j];  j++;  }  k++;  }  // Copy the remaining elements of  // L[], if there are any  while (i < n1) {  arr[k] = L[i];  i++;  k++;  }  // Copy the remaining elements of  // R[], if there are any  while (j < n2) {  arr[k] = R[j];  j++;  k++;  } } // l is for left index and r is // right index of the sub-array // of arr to be sorted function mergeSort(arr,l, r){  if(l>=r){ ritorno;  } var m =l+ parseInt((r-l)/2);  mergeSort(arr,l,m);  mergeSort(arr,m+1,r);  unisci(arr,l,m,r); } // Funzione per stampare un array function printArray( A, size) { for (var i = 0; i< size; i++)  console.log( A[i] + ' '); } var arr = [ 12, 11, 13, 5, 6, 7 ];  var arr_size = arr.length;  console.log( 'Given array is ');  printArray(arr, arr_size);  mergeSort(arr, 0, arr_size - 1);  console.log( 'Sorted array is ');  printArray(arr, arr_size); // This code is contributed by SoumikMondal>
PHP 
 /* PHP recursive program for Merge Sort */ // Merges two subarrays of arr[]. // First subarray is arr[l..m] // Second subarray is arr[m+1..r] function merge(&$arr, $l, $m, $r) { $n1 = $m - $l + 1; $n2 = $r - $m; // Create temp arrays $L = array(); $R = array(); // Copy data to temp arrays L[] and R[] for ($i = 0; $i < $n1; $i++) $L[$i] = $arr[$l + $i]; for ($j = 0; $j < $n2; $j++) $R[$j] = $arr[$m + 1 + $j]; // Merge the temp arrays back into arr[l..r] $i = 0; $j = 0; $k = $l; while ($i < $n1 && $j < $n2) { if ($L[$i] <= $R[$j]) { $arr[$k] = $L[$i]; $i++; } else { $arr[$k] = $R[$j]; $j++; } $k++; } // Copy the remaining elements of L[],  // if there are any while ($i < $n1) { $arr[$k] = $L[$i]; $i++; $k++; } // Copy the remaining elements of R[],  // if there are any while ($j < $n2) { $arr[$k] = $R[$j]; $j++; $k++; } } // l is for left index and r is right index of the // sub-array of arr to be sorted function mergeSort(&$arr, $l, $r) { if ($l < $r) { $m = $l + (int)(($r - $l) / 2); // Sort first and second halves mergeSort($arr, $l, $m); mergeSort($arr, $m + 1, $r); merge($arr, $l, $m, $r); } } // Function to print an array function printArray($A, $size) { for ($i = 0; $i < $size; $i++) echo $A[$i].' '; echo '
'; } // Driver code $arr = array(12, 11, 13, 5, 6, 7); $arr_size = sizeof($arr); echo 'Given array is 
'; printArray($arr, $arr_size); mergeSort($arr, 0, $arr_size - 1); echo '
Sorted array is 
'; printArray($arr, $arr_size); return 0; //This code is contributed by Susobhan Akhuli ?>>
Produzione 
Given array is 12 11 13 5 6 7 Sorted array is 5 6 7 11 12 13>

Analisi della complessità dell'ordinamento di unione:

Complessità temporale:

  • Caso migliore: O(n log n), quando l'array è già ordinato o quasi ordinato.
  • Caso medio: O(n log n), quando l'array è ordinato in modo casuale.
  • Caso peggiore: O(n log n), quando l'array viene ordinato in ordine inverso.

Complessità spaziale: O(n), è richiesto spazio aggiuntivo per l'array temporaneo utilizzato durante l'unione.

Vantaggi dell'ordinamento unito:

  • Stabilità : Merge sort è un algoritmo di ordinamento stabile, il che significa che mantiene l'ordine relativo degli elementi uguali nell'array di input.
  • Prestazioni garantite nel caso peggiore: L'ordinamento di unione ha una complessità temporale nel caso peggiore di O(N logN) , il che significa che funziona bene anche su set di dati di grandi dimensioni.
  • Semplice da implementare: L’approccio divide et impera è semplice.

Svantaggio dell'ordinamento di unione:

  • Complessità spaziale: L'ordinamento di unione richiede memoria aggiuntiva per archiviare i sottoarray uniti durante il processo di ordinamento.
  • Non sul posto: L'ordinamento di unione non è un algoritmo di ordinamento sul posto, il che significa che richiede memoria aggiuntiva per archiviare i dati ordinati. Ciò può rappresentare uno svantaggio nelle applicazioni in cui l'utilizzo della memoria è un problema.

Applicazioni di Merge Sort:

  • Ordinamento di set di dati di grandi dimensioni
  • Ordinamento esterno (quando il set di dati è troppo grande per essere contenuto nella memoria)
  • Conteggio delle inversioni (contare il numero di inversioni in un array)
  • Trovare la mediana di un array

Link veloci:

  • Articoli recenti su Merge Sort
  • Domande e problemi di ordinamento principali dell'intervista
  • Problemi pratici sull'algoritmo di ordinamento
  • Quiz sull'ordinamento une