Al igual que QuickSort , Merge Sort es un algoritmo Divide and Conquer . Divide la array de entrada en dos mitades, se llama a sí mismo para las dos mitades y luego fusiona las dos mitades ordenadas. La función merge() se utiliza para fusionar dos mitades. merge(arr, l, m, r) es un proceso clave que asume que arr[l..m] y arr[m+1..r] están ordenados y fusiona los dos subarreglos ordenados en uno solo.
Pseudocódigo:
• Declare left variable to 0 and right variable to n-1 • Find mid by medium formula. mid = (left+right)/2 • Call merge sort on (left,mid) • Call merge sort on (mid+1,rear) • Continue till left is less than right • Then call merge function to perform merge sort.
Algoritmo:
Step 1: Start Step 2: Declare an array and left, right, mid variable Step 3: Perform merge function. mergesort(array,left,right) mergesort (array, left, right) if left > right return mid= (left+right)/2 mergesort(array, left, mid) mergesort(array, mid+1, right) merge(array, left, mid, right) Step 4: Stop
Consulte la siguiente implementación de C para obtener más detalles.
MergeSort(arr[], l, r)
Si r > l
- Encuentre el punto medio para dividir la array en dos mitades:
- medio m = l + (r – l)/2
- Llame a mergeSort para la primera mitad:
- Llame a mergeSort(arr, l, m)
- Llame a mergeSort para la segunda mitad:
- Llame a mergeSort(arr, m + 1, r)
- Combina las dos mitades ordenadas en los pasos 2 y 3:
- Combinar llamadas (arr, l, m, r)
¿Cómo funciona la ordenación por combinación?
Para conocer el funcionamiento del ordenamiento por fusión, consideremos una array arr[] = {38, 27, 43, 3, 9, 82, 10}
- Al principio, verifique si el índice izquierdo de la array es menor que el índice derecho, si es así, calcule su punto medio
- Ahora, como ya sabemos, la ordenación por fusión primero divide la array completa de forma iterativa en mitades iguales, a menos que se alcancen los valores atómicos.
- Aquí vemos que una array de 7 elementos se divide en dos arrays de tamaño 4 y 3 respectivamente.
- Ahora, vuelva a encontrar que el índice izquierdo es menor que el índice derecho para ambas arrays, si encuentra que sí, luego calcule nuevamente los puntos medios para ambas arrays.
- Ahora, divida aún más estas dos arrays en otras mitades, hasta que se alcancen las unidades atómicas de la array y no sea posible realizar más divisiones.
- Después de dividir la array en unidades más pequeñas, comience a fusionar los elementos nuevamente en función de la comparación del tamaño de los elementos.
- En primer lugar, compare el elemento de cada lista y luego combínelos en otra lista de manera ordenada.
- Después de la fusión final, la lista se ve así:
Consulte las siguientes ilustraciones para mayor claridad:
El siguiente diagrama muestra el proceso completo de clasificación por fusión para una array de ejemplo {38, 27, 43, 3, 9, 82, 10}.
Si observamos más de cerca el diagrama, podemos ver que la array se divide recursivamente en dos mitades hasta que el tamaño se vuelve
- Una vez que el tamaño se convierte en 1, los procesos de fusión entran en acción y comienzan a fusionar arrays hasta que se fusiona la array completa.
C
// C program for Merge Sort #include <stdio.h> #include <stdlib.h> // 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] // Initial index of first subarray i = 0; // Initial index of second subarray j = 0; // Initial index of merged subarray 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) { // Same as (l+r)/2, but avoids // overflow for large l and h 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); } } // UTILITY FUNCTIONS // Function to print an array void printArray(int A[], int size) { int i; for (i = 0; i < size; i++) printf("%d ", A[i]); printf("\n"); } // Driver code int main() { int arr[] = {12, 11, 13, 5, 6, 7}; int arr_size = sizeof(arr) / sizeof(arr[0]); printf("Given array is \n"); printArray(arr, arr_size); mergeSort(arr, 0, arr_size - 1); printf("\nSorted array is \n"); printArray(arr, arr_size); return 0; }
¿Escribir código en un comentario? Utilice ide.geeksforgeeks.org , genere un enlace y compártalo aquí.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA