• Author / Uploaded
• Jose Macias

Citation preview

MergeSort (Ordenamiento por Mezcla)

Está basado en la técnica de “divide y vencerás “. Primero toma el arreglo original de datos, lo divide en dos partes del mismo tamaño cada una, y lo sigue dividiendo hasta que solo quede un elemento. Cada una de las divisiones se ordena de manera separada y luego se unen para formar el arreglo ya ordenado. Este algoritmo divide inicialmente la lista hasta su mínimo valor y luego ordena el arreglo. Ejemplo gráfico Como estamos usando divide y vencerás para ordenar, tenemos que decidir cómo se van a ver nuestros subproblemas. El problema completo es ordenar todo un arreglo. Digamos que un subproblema es ordenar un subarreglo. En particular, vamos a pensar que un subproblema es ordenar el subarreglo que empieza en el índice p y va hasta el índice r. Será conveniente tener una notación para un subarreglo, así que digamos que array[p..r] denota este subarreglo de array. En términos de nuestra notación, para un arreglo de n elementos, podemos decir que el problema original es ordenar array[0..n-1]. Aquí está cómo el ordenamiento por mezcla utiliza divide y vencerás: 1. Divide al encontrar el número q de la posición a medio camino entre p y r. Haz este paso de la misma manera en que encontramos el punto medio en la búsqueda binaria: suma p y r, divide entre 2 y redondea hacia abajo. 2. Vence al ordenar de manera recursiva los subarreglos en cada uno de los dos subproblemas creados por el paso de dividir. Es decir, ordena de manera recursiva el subarreglo array[p..q] y ordena de manera recursiva el subarreglo array[q+1..r]. 3. Combina al mezclar los dos subarreglos ordenados de regreso en un solo subarreglo ordenado array[p..r]. Necesitamos un caso base. El caso base es el subarreglo que contiene menos de dos elementos, es decir, cuando p ≥ r, ya que un subarreglo sin elementos o con solo un elemento ya está ordenado. Así que vamos a dividir-vencer-combinar solo cuando p