El ordenamiento por mezcla es un algoritmo de ordenamiento eficiente basado en la operación de fusión. Este algoritmo es una aplicación muy típica del método de divide y vencerás (Divide and Conquer).

Primero consideremos cómo fusionar dos secuencias ordenadas. Esto es muy simple: basta con comparar el primer número de las dos secuencias, tomar el menor y luego eliminar ese número de la secuencia correspondiente. Luego se vuelve a comparar. Si una de las secuencias queda vacía, simplemente se extraen los datos de la otra secuencia en orden.

// Fusiona los arrays ordenados a[] y b[] en c[] void MemeryArray(int a[], int n, int b[], int m, int c[]) { int i, j, k; i = j = k = 0; while (i < n && j < m) { if (a[i] < b[j]) c[k++] = a[i++]; else c[k++] = b[j++]; } while (i < n) c[k++] = a[i++]; while (j < m) c[k++] = b[j++]; }

Se puede ver que la eficiencia de fusionar secuencias ordenadas es relativamente alta, pudiendo alcanzar O(n).

Una vez resuelto el problema de fusionar secuencias ordenadas, veamos el ordenamiento por mezcla. Su idea básica es dividir el array en dos grupos A y B. Si los datos dentro de cada grupo están ordenados, entonces es muy conveniente ordenar estos dos grupos. ¿Cómo lograr que los datos dentro de estos dos grupos estén ordenados?

Se puede dividir cada grupo A y B en dos subgrupos. Y así sucesivamente. Cuando un subgrupo dividido tiene un solo dato, se puede considerar que ese subgrupo ya está ordenado internamente, y luego basta con fusionar los dos subgrupos adyacentes. De esta manera, primero se descompone recursivamente la secuencia y luego se fusionan las secuencias, completando así el ordenamiento por mezcla.

// Fusiona dos secuencias ordenadas a[first...mid] y a[mid...last]. void mergearray(int a[], int first, int mid, int last, int temp[]) { int i = first, j = mid + 1; int m = mid, n = last; int k = 0; while (i <= m && j <= n) { if (a[i] <= a[j]) temp[k++] = a[i++]; else temp[k++] = a[j++]; } while (i <= m) temp[k++] = a[i++]; while (j <= n) temp[k++] = a[j++]; for (i = 0; i < k; i++) a[first + i] = temp[i]; } void mergesort(int a[], int first, int last, int temp[]) { if (first < last) { int mid = (first + last) / 2; mergesort(a, first, mid, temp); // Lado izquierdo ordenado mergesort(a, mid + 1, last, temp); // Lado derecho ordenado mergearray(a, first, mid, last, temp); // Luego fusiona las dos secuencias ordenadas } } bool MergeSort(int a[], int n) { int *p = new int[n]; if (p == NULL) return false; mergesort(a, 0, n - 1, p); delete[] p; return true; }

La eficiencia del ordenamiento por mezcla es relativamente alta. Suponiendo que la longitud de la secuencia es N, se necesitan logN pasos en total para dividir la secuencia en subsecuencias pequeñas. Cada paso es un proceso de fusión de secuencias ordenadas, y su complejidad temporal se puede registrar como O(N), por lo que en total es O(N*logN). Debido a que el ordenamiento por mezcla opera siempre sobre datos adyacentes, también es relativamente eficiente entre los métodos de ordenamiento de O(N*logN) (ordenamiento rápido, ordenamiento por mezcla, ordenamiento de Shell, ordenamiento por montículos).

En mi computadora, se compararon el ordenamiento de burbuja, el ordenamiento por inserción directa, el ordenamiento por mezcla y el uso directo de la función qsort() del sistema (todos en versión Release).

Prueba con 20000 datos aleatorios:

Prueba con 50000 datos aleatorios:

Prueba adicional con 200000 datos aleatorios:

Nota: algunos libros asignan un array temporal al fusionar secuencias ordenadas en mergearray(), pero demasiadas operaciones new consumen mucho tiempo. Por lo tanto, se hizo un pequeño cambio: solo se crea un array temporal con new en MergeSort(). Las operaciones posteriores comparten este único array temporal.

Autor: MoreWindows

Original: https://blog.csdn.net/morewindows/article/details/6678165