La ordenación por fusiónEl algoritmo es un algoritmo de clasificación que se considera un ejemplo de la estrategia divide y vencerás. Entonces, en este algoritmo, la array se divide inicialmente en dos mitades iguales y luego se combinan de manera ordenada. Podemos pensar en él como un algoritmo recursivo que divide continuamente la array por la mitad hasta que ya no se puede dividir más. Esto significa que si la array se vacía o solo le queda un elemento, la división se detendrá, es decir, es el caso base para detener la recursividad. Si la array tiene varios elementos, dividimos la array en mitades e invocamos recursivamente el ordenamiento por fusión en cada una de las mitades. Finalmente, cuando ambas mitades están ordenadas, se aplica la operación de fusión. La operación de fusión es el proceso de tomar dos arreglos ordenados más pequeños y combinarlos para eventualmente formar uno más grande.
Pseudocódigo:
C++
// C++ program for Merge Sort #include <iostream> 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) { auto const subArrayOne = mid - left + 1; auto 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, // Initial index of first sub-array indexOfSubArrayTwo = 0; // Initial index of second sub-array int indexOfMergedArray = left; // Initial index of merged array // 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 >= end) return; // Returns recursively auto mid = begin + (end - begin) / 2; mergeSort(array, begin, mid); mergeSort(array, mid + 1, end); merge(array, begin, mid, end); } // UTILITY FUNCTIONS // Function to print an array void printArray(int A[], int size) { for (auto i = 0; i < size; i++) cout << A[i] << " "; } // Driver code int main() { int arr[] = { 12, 11, 13, 5, 6, 7 }; auto arr_size = sizeof(arr) / sizeof(arr[0]); cout << "Given array is \n"; printArray(arr, arr_size); mergeSort(arr, 0, arr_size - 1); cout << "\nSorted array is \n"; 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 <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]*/ i = 0; // Initial index of first subarray j = 0; // Initial index of second subarray k = l; // Initial index of merged subarray 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; }
Java
/* Java program for Merge Sort */ 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 indexes 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"); printArray(arr); MergeSort ob = new MergeSort(); ob.sort(arr, 0, arr.length - 1); System.out.println("\nSorted array"); printArray(arr); } } /* This code is contributed by Rajat Mishra */
Python3
# 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", end="\n") printList(arr) mergeSort(arr) print("Sorted array is: ", end="\n") printList(arr) # This code is contributed by Mayank Khanna
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"); printArray(arr); MergeSort ob = new MergeSort(); ob.sort(arr, 0, arr.Length - 1); Console.WriteLine("\nSorted array"); printArray(arr); } } // This code is contributed by Princi Singh
Javascript
<script> // 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){ return;//returns recursively } var m =l+ parseInt((r-l)/2); mergeSort(arr,l,m); mergeSort(arr,m+1,r); merge(arr,l,m,r); } // UTILITY FUNCTIONS // Function to print an array function printArray( A, size) { for (var i = 0; i < size; i++) document.write( A[i] + " "); } var arr = [ 12, 11, 13, 5, 6, 7 ]; var arr_size = arr.length; document.write( "Given array is <br>"); printArray(arr, arr_size); mergeSort(arr, 0, arr_size - 1); document.write( "<br>Sorted array is <br>"); printArray(arr, arr_size); // This code is contributed by SoumikMondal </script>
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