Scribd
Cargar
8 vistas1 página

Método MergeSort: Algoritmo de Ordenación

El método MergeSort es un algoritmo de ordenación recursivo que divide el array en mitades de tamaño similar, ordena cada mitad de forma recursiva, y luego mezcla las mitades ordenadas en una secuencia ordenada completa. Funciona dividiendo el problema en subproblemas más pequeños hasta que los arrays contienen un solo elemento, y luego reconstruye la solución combinando las soluciones de los subproblemas.

Cargado por

Isabel Garcia
Derechos de autor
© All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd
8 vistas1 página

Método MergeSort: Algoritmo de Ordenación

El método MergeSort es un algoritmo de ordenación recursivo que divide el array en mitades de tamaño similar, ordena cada mitad de forma recursiva, y luego mezcla las mitades ordenadas en una secuencia ordenada completa. Funciona dividiendo el problema en subproblemas más pequeños hasta que los arrays contienen un solo elemento, y luego reconstruye la solución combinando las soluciones de los subproblemas.

Cargado por

Isabel Garcia
Derechos de autor
© All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOCX, PDF, TXT o lee en línea desde Scribd

El método MergeSort

El método MergeSort es un algoritmo de ordenación recursivo con un número


de comparaciones entre elementos del array mínimo.

Su funcionamiento es similar al Quicksort, y está basado en la técnica divide y


vencerás.

De forma resumida el funcionamiento del método MergeSort es el siguiente:

- Si la longitud del array es menor o igual a 1 entonces ya está ordenado.

- El array a ordenar se divide en dos mitades de tamaño similar.

- Cada mitad se ordena de forma recursiva aplicando el método MergeSort.

- A continuación las dos mitades ya ordenadas se mezclan formando una


secuencia ordenada.

El método ordena un array A de enteros desde la posición izq hasta la


posición der. En la primera llamada al método recibirá los valores izq = 0, der =
ELEMENTOS-1.

Primero se calcula el elemento central m. A continuación la primera parte del


array, desde izq hasta m y la segunda parte del array, desde m+1 hasta der, se
mezclan mediante llamadas recursivas al método mergesort.

La recursión termina cuando izq == der, es decir, cuando un subarray contiene


solamente un elemento.

La operación principal de mezcla la realiza el método merge.

De forma gráfica podemos representar el funcionamiento del algoritmo de la


siguiente forma

También podría gustarte