Merge Sort
Merge Sort
•
Este algoritmo tambien es llamado de
Intercalación o combinación, debido
que combina (intercala) dos
estructuras previamente ordenadas.
Merge Sort

Supongamos los siguientes vectores
previamente ordenados, el nuevo vector
contendra la cantidad de elementos de
ambos
3
5
8
12 17
1
6
9
Se comparan los primeros elementos 3 y 1, el menor se copia
24
Merge Sort
1
Se copia el valor del vector B y los subindices K y J, se mueven
una posición
3
5
8
12 17
1
6
9
24
Se comparan los siguientes valores 3 y 6, se mueve el menor
Merge Sort
1
3
Se copia el valor del vector A y los subindices K e I, se mueven
una posición
3
5
8
12 17
1
6
9
24
Se comparan los siguientes valores 5 y 6, se mueve el menor
Merge Sort
1
3
5
Se copia el valor del vector A y los subindices K e I, se mueven
una posición
3
5
8
12 17
1
6
9
24
Se comparan los siguientes valores 8 y 6, se mueve el menor
Merge Sort
1
3
5
6
Se copia el valor del vector B y los subindices K y J, se mueven
una posición
3
5
8
12 17
1
6
9
24
Se comparan los siguientes valores 8 y 9, se mueve el menor
Merge Sort
1
3
5
6
8
Se copia el valor del vector A y los subindices K e I, se mueven
una posición
3
5
8
12 17
1
6
9
24
Se comparan los siguientes valores 12 y 9, se mueve el menor
Merge Sort
1
3
5
6
8
9
Se copia el valor del vector B y los subindices K y J, se mueven
una posición
3
5
8
12 17
1
6
9
24
Se comparan los siguientes valores 12 y 24, se mueve el menor
Merge Sort
1
3
5
6
8
9
12
Se copia el valor del vector A y los subindices K e I, se mueven
una posición
3
5
8
12 17
1
6
9
24
Se comparan los siguientes valores 17 y 24, se mueve el menor
Merge Sort
De igual forma se sigue con los siguientes valores hasta
completar el recorrido
1
3
5
6
8
9
12 17 24
El proceso termina cuando uno de los dos subindices I o J,
llega hasta la longitud del vector.
En ese momento se termina de copiar los siguientes valores
del vector
Merge Sort
void merge(int f, int m, int l,
int *a,int n)
{
int i,j,k,b[n];
for(i=f;i<=l;i++)
b[i] = a[i];
i = k = f;
j = m+1;
while(i<=m && j<=l)
{
if(b[i]<b[j]) a[k++] =
b[i++];
else a[k++] =
b[j++];
}
while(i<=m) a[k++] =
b[i++];
while(j<=l) a[k++] =
b[j++];
}
Merge Sort

Se puede utilizar este algoritmo para
ordenar un vector.
void mergeSort(int first, int last, int *a, int n)
{
Int mid;
if(last>first)
{
mid=(first+last)/2;
mergeSort(first,mid,a,n);
mergeSort(mid+1,last,a,n);
merge(first,mid,last,a,n);
}
}
Merge Sort
Descargar

MergeSort