Blox - Donde la lógica se vuelve natural

Nombre

MergeSort - Ordena un vector usando el algoritmo MergeSort.

Sinopsis

out = merge.MergeSort(A, inicio, fin)

Descripcion

Aplica el esquema clasico de divide y venceras para ordenar el rango indicado de un vector.

Divide el problema en dos mitades, ordena cada mitad recursivamente y luego las vuelve a combinar con merge.Mezclar().

Comportamiento

Calcula el punto medio del rango como (inicio + fin) / 2 y lo convierte a entero.
Ordena recursivamente la mitad izquierda y la mitad derecha.
Usa merge.Mezclar() para fusionar las dos mitades ya ordenadas.
Si inicio >= fin, no subdivide mas el problema.
Retorna el vector A ordenado en el rango solicitado.

Funciones API relacionadas

merge.Mezclar()

Parámetros

Parámetro	Tipo	Descripción
A	MATRIZ	Matriz o vector principal de entrada.
inicio	NUMERICO	Indice inicial del rango a ordenar.
fin	NUMERICO	Indice final del rango a ordenar.

Valor de retorno

VECTOR - Vector A ordenado.

Ejemplo

ejemplo.blox

FUNCION MergeSort(A, inicio, fin)
FUNCION Mezclar(A, inicio, medio, fin)

FUNCION PRINCIPAL
INICIO  "Ordenar un Vector - MERGE SORT"

     NUMERICO  I
     VECTOR    A[1000]
     NUMERICO  Cant

    Cant = A.dim

    IMPRIMIR ("\n   Asignando valores al Vector....\n\n")

    I = 0
    MIENTRAS (I < Cant) HACER
       A[I] = ALEATORIO(Cant)
       I = I + 1
    FIN_MIENTRAS

    IMPRIMIR ("\n   Calculando. Aguarde....\n")

    // Llamada principal a MergeSort
    MergeSort(A, 0, Cant-1)
    
    IMPRIMIR ("\n   Vector Ordenado ")
    IMPRIMIR ("\n  __________________\n")

    DEPURAR(A)
    IMPRIMIR ("\n")

FINAL





FUNCION Mezclar(A, inicio, medio, fin)
INICIO
    
    NUMERICO i, j, k
    NUMERICO n1, n2
    // Crea subarreglos temporales
    n1 = medio - inicio + 1
    n2 = fin - medio

    
    VECTOR Izquierda[n1], Derecha[n2]

    // Copia datos a los subarreglos temporales
    PARA i = 0  HASTA n1-1 HACER 
        Izquierda[i] = A[inicio + i]
    FIN_PARA

    PARA j = 0 HASTA n2-1 HACER 
        Derecha[j] = A[medio + 1 + j]
    FIN_PARA

    // Fusiona los subarreglos temporales de vuelta en A[inicio..fin]
    i = 0
    j = 0
    k = inicio
    MIENTRAS (i < n1 & j < n2) HACER
        SI (Izquierda[i] <= Derecha[j]) ENTONCES
            A[k] = Izquierda[i]
            i = i + 1
        SINO
            A[k] = Derecha[j]
            j = j + 1
        FIN_SI
        k = k + 1
    FIN_MIENTRAS

    // Copia los elementos restantes de Izquierda (si los hay)
    MIENTRAS (i < n1) HACER
        A[k] = Izquierda[i]
        i = i + 1
        k = k + 1
    FIN_MIENTRAS

    // Copia los elementos restantes de Derecha (si los hay)
    MIENTRAS (j < n2) HACER
        A[k] = Derecha[j]
        j = j + 1
        k = k + 1
    FIN_MIENTRAS

    //RETORNAR A
FINAL_FUNCION




FUNCION MergeSort(A, inicio, fin)
INICIO

    NUMERICO medio

    //IMPRIMIR("\ninicio = ", inicio, ", fin = ", fin)
    

    SI (inicio < fin) ENTONCES
        // 1. Dividir
        medio = (inicio + fin) / 2          // Calcula el punto medio
        medio = ENTERO(medio)
        
        // 2. Vencer (Recursión)
        MergeSort(A, inicio, medio)      // Ordena la mitad izquierda
        MergeSort(A, medio + 1, fin)     // Ordena la mitad derecha

        // 3. Combinar
        Mezclar(A, inicio, medio, fin)     // Fusiona las dos mitades ordenadas      
    FIN_SI

    //RETORNAR A
FINAL_FUNCION

MergeSort(A,inicio,fin)\texttt{MergeSort}(A, inicio, fin)MergeSort(A,inicio,fin)

Parámetros

Valor de retorno

Ejemplo

$\texttt{MergeSort}(A, inicio, fin)$