Guía Definitiva de Merge Sort: El Algoritmo de Divide y Vencerás

Source: Dev.to

Introducción

Merge Sort es un algoritmo de ordenamiento basado en el paradigma Divide y Vencerás. Divide recursivamente el arreglo en mitades hasta llegar a elementos individuales (ordenados por definición) y luego los mezcla de forma ordenada. Garantiza un rendimiento de O(n log n) en todos los casos.

El algoritmo (también llamado Ordenamiento por Mezcla) es uno de los pilares del ordenamiento en ciencias de la computación. Se destaca cuando requerimos estabilidad y rendimiento garantizado.

Fases del algoritmo

1. Divide
   El arreglo se parte a la mitad de forma recursiva hasta llegar a elementos individuales, los cuales se consideran ya ordenados.

2. Conquista (Conquer)
   Cada sub‑división se resuelve y ordena de forma independiente.

3. Combina (Merge)
   Se unen o “mezclan” las piezas usando la técnica de two‑pointers, garantizando que las combinaciones resultantes sigan estando ordenadas.

A diferencia del popular QuickSort, Merge Sort siempre asegura una complejidad de tiempo de ejecución de O(n log n) en cualquier escenario (mejor caso, caso promedio y peor caso). Sin embargo, este rendimiento constante tiene un costo: mayor uso de memoria RAM.

Implementación legible en Go

func sortList(unsortedList []int) []int {
    n := len(unsortedList)
    if n <= 1 {
        return unsortedList
    }

    midpoint := n / 2
    leftList := sortList(unsortedList[:midpoint])
    rightList := sortList(unsortedList[midpoint:])

    resultList := make([]int, 0, n)
    leftPointer, rightPointer := 0, 0

    for leftPointer < midpoint || rightPointer < n-midpoint {
        if leftPointer == midpoint {
            resultList = append(resultList, rightList[rightPointer])
            rightPointer++
        } else if rightPointer == n-midpoint {
            resultList = append(resultList, leftList[leftPointer])
            leftPointer++
        } else if leftList[leftPointer] <= rightList[rightPointer] {
            resultList = append(resultList, leftList[leftPointer])
            leftPointer++
        } else {
            resultList = append(resultList, rightList[rightPointer])
            rightPointer++
        }
    }
    return resultList
}

Esta versión es clara y fácil de depurar, pero crea un nuevo slice en cada llamada recursiva, lo que implica asignaciones de memoria dinámicas y presión sobre el garbage collector.

Optimización con el Patrón de Búfer Compartido

Para entornos de alta escala o bibliotecas estándar, es preferible asignar un único buffer auxiliar que se reutilice durante toda la recursividad.

func SortList(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }

    // Un solo buffer auxiliar compartido para toda la ejecución
    temp := make([]int, len(arr))
    mergeSort(arr, temp, 0, len(arr)-1)
    return arr
}

func mergeSort(arr, temp []int, left, right int) {
    if left < right {
        mid := left + (right-left)/2

        mergeSort(arr, temp, left, mid)
        mergeSort(arr, temp, mid+1, right)

        merge(arr, temp, left, mid, right)
    }
}

func merge(arr, temp []int, left, mid, right int) {
    // Copiar el segmento actual al buffer temporal
    for i := left; i <= right; i++ {
        temp[i] = arr[i]
    }

    i, j, k := left, mid+1, left

    // Fusionar de nuevo en el arreglo original
    for i <= mid && j <= right {
        if temp[i] <= temp[j] {
            arr[k] = temp[i]
            i++
        } else {
            arr[k] = temp[j]
            j++
        }
        k++
    }

    // Copiar los elementos restantes del sub‑arreglo izquierdo (si los hay)
    for i <= mid {
        arr[k] = temp[i]
        i++
        k++
    }
}

Con este enfoque la memoria adicional se mantiene en O(N) estrictamente; sin importar cuántas fusiones o subdivisiones ocurran, nunca se excede el tamaño original del búfer.

Conclusión

Merge Sort destaca por su solidez matemática y su comportamiento estable en tiempo de ejecución. Aunque su consumo de memoria suele inclinar a los desarrolladores hacia QuickSort, técnicas como el Shared Buffer Pattern reducen significativamente el overhead, devolviendo a Merge Sort a un lugar protagónico, especialmente en:

• Ordenamiento de listas enlazadas, donde el acceso secuencial es natural.
• Aplicaciones que requieren estabilidad y rendimiento garantizado a gran escala.