Blox - Donde la lógica se vuelve natural

Nombre

Mezclar - Mezcla dos subarreglos ordenados dentro de A como parte del algoritmo MergeSort.

Sinopsis

out = merge.Mezclar(A, inicio, medio, fin)

Descripcion

Fusiona dos tramos consecutivos ya ordenados dentro de un mismo vector o matriz lineal.

Se usa como paso de combinacion del algoritmo MergeSort, tomando un bloque izquierdo A[inicio..medio] y un bloque derecho A[medio+1..fin] para reconstruir el rango ordenado completo.

Comportamiento

Calcula los tamanos de los dos subarreglos temporales.
Copia los elementos del tramo izquierdo y del tramo derecho en buffers auxiliares.
Recorre ambos buffers comparando sus elementos para reconstruir A[inicio..fin] en orden.
Copia al final los elementos restantes del lado izquierdo o derecho si todavia quedan.
Retorna A con el tramo ya fusionado y ordenado.

Funciones API relacionadas

merge.MergeSort()

Parámetros

Parámetro	Tipo	Descripción
A	MATRIZ	Matriz o vector principal de entrada.
inicio	NUMERICO	Indice inicial del rango a mezclar.
medio	NUMERICO	Punto medio que separa las dos mitades ya ordenadas.
fin	NUMERICO	Indice final del rango a mezclar.

Valor de retorno

VECTOR - Vector A con el tramo inicio..fin mezclado y 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

Mezclar(A,inicio,medio,fin)\texttt{Mezclar}(A, inicio, medio, fin)Mezclar(A,inicio,medio,fin)

Parámetros

Valor de retorno

Ejemplo

$\texttt{Mezclar}(A, inicio, medio, fin)$