Notación Big O: introducción y ejemplos

La notación Big O es una herramienta fundamental para describir la eficiencia de un algoritmo en términos de tiempo y espacio. Mediante esta notación, podemos expresar cómo se comporta el tiempo de ejecución o el uso de memoria de un algoritmo a medida que aumenta el tamaño de la entrada.

Consideremos un ejemplo sencillo: supongamos que tenemos un algoritmo que recorre una lista de n elementos para calcular la suma total. El tiempo que tarda en ejecutarse es proporcional al número de elementos, por lo que podemos decir que su complejidad temporal es O(n).

En PseInt, podríamos implementar este algoritmo de la siguiente manera:

Proceso SumaElementos
    // Declarar un tamaño máximo para el arreglo
    Definir MAX_SIZE Como Entero
    MAX_SIZE <- 100
    
    // Declarar el arreglo con un tamaño fijo
    Dimension lista[MAX_SIZE]
    
    // Declarar variables
    Definir suma, n, i Como Entero
    
    // Inicializar la suma
    suma <- 0
    
    // Leer el número de elementos
    Escribir "Ingrese el número de elementos (máximo ", MAX_SIZE, "):"
    Leer n
    
    // Validar que n no exceda el tamaño máximo
    Si n > MAX_SIZE Entonces
        Escribir "El número de elementos excede el tamaño máximo permitido."
    FinSi

    // Leer los elementos de la lista
    Para i <- 1 Hasta n Hacer
        Escribir "Ingrese el elemento ", i, ":"
        Leer lista[i]
        suma <- suma + lista[i]
    Fin Para

    // Mostrar la suma total
    Escribir "La suma total es: ", suma
FinProceso

En Python, el código equivalente sería:

def suma_elementos():
    lista = []
    suma = 0
    n = int(input("Ingrese el número de elementos: "))
    for i in range(n):
        elemento = int(input(f"Ingrese el elemento {i+1}: "))
        lista.append(elemento)
        suma += elemento
    print(f"La suma total es: {suma}")

Otro caso común es el algoritmo de búsqueda binaria, cuya complejidad es O(log n). Esto significa que el tiempo de ejecución crece logarítmicamente con respecto al tamaño de la entrada, lo que es más eficiente que un crecimiento lineal.

El pseudocódigo de la búsqueda binaria en Python sería:

def busqueda_binaria(lista, objetivo):
    inicio = 0
    fin = len(lista) - 1
    while inicio <= fin:
        medio = (inicio + fin) // 2
        if lista[medio] == objetivo:
            print(f"Elemento encontrado en la posición: {medio}")
            return
        elif lista[medio] < objetivo:
            inicio = medio + 1
        else:
            fin = medio - 1
    print("Elemento no encontrado")

La importancia de entender la complejidad algorítmica radica en la selección del algoritmo más eficiente para un problema dado. Por ejemplo, un algoritmo con complejidad O(n^2) puede ser aceptable para conjuntos de datos pequeños, pero ineficiente para conjuntos grandes.

Veamos un ejemplo de un algoritmo con complejidad O(n^2), como el ordenamiento por burbuja:

Proceso OrdenamientoBurbuja
    // Definir un tamaño máximo para el arreglo
    Definir MAX_SIZE Como Entero
    MAX_SIZE <- 100
    
    // Declarar el arreglo con un tamaño fijo
    Dimension lista[MAX_SIZE]
    
    // Declarar variables
    Definir suma, n, i, j, aux Como Entero
    
    // Inicializar la lista
    suma <- 0
    
    // Leer el número de elementos
    Escribir "Ingrese el número de elementos (máximo ", MAX_SIZE, "):"
    Leer n
    
    // Validar que n no exceda el tamaño máximo
    Si n > MAX_SIZE Entonces
        Escribir "El número de elementos excede el tamaño máximo permitido."
    FinSi

    // Leer los elementos de la lista
    Para i <- 1 Hasta n Hacer
        Escribir "Ingrese el elemento ", i, ":"
        Leer lista[i]
    Fin Para

    // Implementar el Ordenamiento por Burbuja
    Para i <- 1 Hasta n-1 Hacer
        Para j <- 1 Hasta n - i Hacer
            Si lista[j] > lista[j+1] Entonces
                // Intercambio de elementos
                aux <- lista[j]
                lista[j] <- lista[j+1]
                lista[j+1] <- aux
            FinSi
        Fin Para
    Fin Para

    // Mostrar la lista ordenada
    Escribir "La lista ordenada es:"
    Para i <- 1 Hasta n Hacer
        Escribir lista[i]
    Fin Para
FinProceso

Y su equivalente en Python:

def ordenamiento_burbuja(lista):
    n = len(lista)
    for i in range(n-1):
        for j in range(n - i - 1):
            if lista[j] > lista[j+1]:
                lista[j], lista[j+1] = lista[j+1], lista[j]

Por último, es esencial reconocer que algunos problemas requieren algoritmos más eficientes. Por ello, es recomendable utilizar algoritmos con complejidad O(n log n), como el ordenamiento rápido. Comprender la notación Big O nos permite tomar decisiones informadas al diseñar y seleccionar algoritmos adecuados para nuestras aplicaciones.

Análisis de complejidad en algoritmos de ordenamiento y búsqueda

El análisis de complejidad en algoritmos de ordenamiento y búsqueda es esencial para entender su eficiencia y seleccionar el más adecuado según el contexto. Al examinar cómo crece el tiempo de ejecución con respecto al tamaño de la entrada, podemos anticipar el rendimiento y las limitaciones de cada algoritmo.

En algoritmos de ordenamiento, uno de los más básicos es el ordenamiento por inserción. Este algoritmo construye el arreglo ordenado de manera incremental, insertando cada elemento en su posición correcta. Su complejidad temporal en el peor caso es O(n²), ya que para cada elemento puede ser necesario compararlo con todos los anteriores.

El pseudocódigo en PseInt para el ordenamiento por inserción es:

Proceso OrdenamientoInsercion
    // Definir un tamaño máximo para el arreglo
    Definir MAX_SIZE Como Entero
    MAX_SIZE <- 100
    
    // Declarar el arreglo con un tamaño fijo
    Dimension lista[MAX_SIZE]
    
    // Declarar variables
    Definir suma, n, i, j, valorActual Como Entero
    
    // Inicializar la suma (opcional, en este caso no se usa)
    suma <- 0
    
    // Leer el número de elementos
    Escribir "Ingrese el número de elementos (máximo ", MAX_SIZE, "):"
    Leer n
    
    // Validar que n no exceda el tamaño máximo
    Si n > MAX_SIZE Entonces
        Escribir "El número de elementos excede el tamaño máximo permitido."
    FinSi

    // Leer los elementos de la lista
    Para i <- 1 Hasta n Hacer
        Escribir "Ingrese el elemento ", i, ":"
        Leer lista[i]
    Fin Para

    // Implementar el Ordenamiento por Inserción
    Para i <- 2 Hasta n Hacer
        valorActual <- lista[i]
        j <- i - 1
        
        Mientras j > 0 Y lista[j] > valorActual Hacer
            lista[j + 1] <- lista[j]
            j <- j - 1
        Fin Mientras
        
        lista[j + 1] <- valorActual
    Fin Para

    // Mostrar la lista ordenada
    Escribir "La lista ordenada es:"
    Para i <- 1 Hasta n Hacer
        Escribir lista[i]
    Fin Para
FinProceso

El equivalente en Python sería:

def ordenamiento_insercion(lista):
    for i in range(1, len(lista)):
        valor_actual = lista[i]
        j = i - 1
        while j >= 0 and lista[j] > valor_actual:
            lista[j + 1] = lista[j]
            j -= 1
        lista[j + 1] = valor_actual

En contraste, el ordenamiento por mezcla o Merge Sort es un algoritmo más eficiente con una complejidad de O(n log n). Este algoritmo utiliza la estrategia de divide y vencerás, dividiendo el conjunto en mitades, ordenando cada mitad y luego combinándolas.

En Python para el ordenamiento por mezcla es:

def ordenamiento_mezcla(lista):
    if len(lista) <= 1:
        return lista
    medio = len(lista) // 2
    izquierda = lista[:medio]
    derecha = lista[medio:]
    izquierda = ordenamiento_mezcla(izquierda)
    derecha = ordenamiento_mezcla(derecha)
    return mezclar(izquierda, derecha)

def mezclar(izquierda, derecha):
    resultado = []
    i = j = 0
    while i < len(izquierda) and j < len(derecha):
        if izquierda[i] <= derecha[j]:
            resultado.append(izquierda[i])
            i += 1
        else:
            resultado.append(derecha[j])
            j += 1
    resultado.extend(izquierda[i:])
    resultado.extend(derecha[j:])
    return resultado

El ordenamiento rápido o Quick Sort es otro algoritmo eficiente con complejidad promedio de O(n log n). Sin embargo, en el peor caso su complejidad puede degradarse a O(n²) si los pivotes seleccionados no son óptimos.

El Python para el ordenamiento rápido es:

def ordenamiento_rapido(lista):
    def quicksort(lista, inicio, fin):
        if inicio < fin:
            pivote = particionar(lista, inicio, fin)
            quicksort(lista, inicio, pivote - 1)
            quicksort(lista, pivote + 1, fin)
    def particionar(lista, inicio, fin):
        pivote = lista[fin]
        i = inicio - 1
        for j in range(inicio, fin):
            if lista[j] <= pivote:
                i += 1
                lista[i], lista[j] = lista[j], lista[i]
        lista[i + 1], lista[fin] = lista[fin], lista[i + 1]
        return i + 1
    quicksort(lista, 0, len(lista) - 1)

En cuanto a algoritmos de búsqueda, la búsqueda lineal tiene una complejidad de O(n), ya que en el peor caso es necesario recorrer todos los elementos. En contraste, la búsqueda binaria, como vimos anteriormente, tiene una complejidad de O(log n), siempre que la lista esté ordenada.

El pseudocódigo para la búsqueda lineal en PseInt es:

Algoritmo BusquedaLineal
    // Definir un tamaño máximo para el arreglo
    Definir MAX_SIZE Como Entero
    MAX_SIZE <- 100
    
    // Declarar el arreglo con un tamaño fijo
    Dimension lista[MAX_SIZE]
    
    // Declarar variables
    Definir n, i, objetivo Como Entero
    Definir encontrado Como Logico
    
    // Inicializar la variable 'encontrado'
    encontrado <- Falso
    
    // Leer el número de elementos
    Escribir "Ingrese el número de elementos (máximo ", MAX_SIZE, "):"
    Leer n
    
    // Validar que n no exceda el tamaño máximo
    Si n > MAX_SIZE Entonces
        Escribir "El número de elementos excede el tamaño máximo permitido."
    Fin Si

    // Leer los elementos de la lista
    Para i <- 1 Hasta n Hacer
        Escribir "Ingrese el elemento ", i, ":"
        Leer lista[i]
    Fin Para

    // Leer el objetivo a buscar
    Escribir "Ingrese el valor a buscar:"
    Leer objetivo

    // Realizar la búsqueda lineal
    Para i <- 1 Hasta n Hacer
        Si lista[i] = objetivo Entonces
            Escribir "Elemento encontrado en la posición: ", i
            encontrado <- Verdadero
            Fin Si
        Fin Para
        
        // Mostrar el resultado si no se encontró el elemento
        Si encontrado = Falso Entonces
            Escribir "Elemento no encontrado en la lista."
        Fin Si
FinAlgoritmo

Y en Python:

def busqueda_lineal(lista, objetivo):
    for i in range(len(lista)):
        if lista[i] == objetivo:
            print(f"Elemento encontrado en la posición: {i}")
            return
    print("Elemento no encontrado")

Es importante destacar que el análisis de complejidad espacial también es relevante. Por ejemplo, el ordenamiento por mezcla requiere espacio adicional proporcional a O(n) para las listas auxiliares, mientras que algoritmos como el ordenamiento por inserción trabajan en el lugar y utilizan O(1) espacio extra.

Comprender estas complejidades permite a los desarrolladores elegir algoritmos que optimicen el uso de recursos según las necesidades específicas, ya sea priorizando el tiempo de ejecución o minimizando el uso de memoria.

Comparación de costos computacionales: tiempo vs. espacio

Al desarrollar algoritmos, es fundamental considerar no solo el tiempo de ejecución sino también el espacio de memoria que utilizan. Estos dos factores representan los costos computacionales principales y, en muchas ocasiones, optimizar uno implica sacrificar el otro. Entender este equilibrio es clave para diseñar soluciones eficientes y adecuadas a las restricciones del problema.

Imaginemos un escenario en el que necesitamos ordenar una gran cantidad de datos. Podemos optar por el ordenamiento por burbuja, que tiene una complejidad temporal de O(n²) y un uso de memoria O(1), o por el ordenamiento por mezcla, con complejidad temporal de O(n log n) pero un consumo de memoria adicional de O(n). Aunque el ordenamiento por mezcla es más rápido, requiere espacio extra para las listas temporales.

En PseInt, el ordenamiento por burbuja se implementa de la siguiente manera:

Algoritmo OrdenamientoBurbuja
    // Definir un tamaño máximo para el arreglo
    Definir MAX_SIZE Como Entero
    MAX_SIZE <- 100
    
    // Declarar el arreglo con un tamaño fijo
    Dimension lista[MAX_SIZE]
    
    // Declarar variables
    Definir n, i, j, aux Como Entero
    
    // Leer el número de elementos
    Escribir "Ingrese el número de elementos (máximo ", MAX_SIZE, "):"
    Leer n
    
    // Validar que n no exceda el tamaño máximo
    Si n > MAX_SIZE Entonces
        Escribir "El número de elementos excede el tamaño máximo permitido."
    Fin Si

    // Leer los elementos de la lista
    Para i <- 1 Hasta n Hacer
        Escribir "Ingrese el elemento ", i, ":"
        Leer lista[i]
    Fin Para

    // Implementar el Ordenamiento por Burbuja
    Para i <- 1 Hasta n-1 Hacer
        Para j <- 1 Hasta n - i Hacer
            Si lista[j] > lista[j+1] Entonces
                // Intercambio de elementos
                aux <- lista[j]
                lista[j] <- lista[j+1]
                lista[j+1] <- aux
            Fin Si
        Fin Para
    Fin Para

    // Mostrar la lista ordenada
    Escribir "La lista ordenada es:"
    Para i <- 1 Hasta n Hacer
        Escribir lista[i]
    Fin Para
FinAlgoritmo

Y su equivalente en Python:

def ordenamiento_burbuja(lista):
    n = len(lista)
    for i in range(n - 1):
        for j in range(n - i - 1):
            if lista[j] > lista[j + 1]:
                lista[j], lista[j + 1] = lista[j + 1], lista[j]

Este algoritmo es sencillo y consume poca memoria adicional, pero su tiempo de ejecución es elevado para listas grandes. Por otro lado, el ordenamiento por mezcla mejora el tiempo a costa de utilizar más memoria. En Python, el código sería:

def ordenamiento_mezcla(lista):
    if len(lista) <= 1:
        return lista
    medio = len(lista) // 2
    izquierda = lista[:medio]
    derecha = lista[medio:]
    izquierda = ordenamiento_mezcla(izquierda)
    derecha = ordenamiento_mezcla(derecha)
    return mezclar(izquierda, derecha)

def mezclar(izquierda, derecha):
    resultado = []
    i = j = 0
    while i < len(izquierda) and j < len(derecha):
        if izquierda[i] <= derecha[j]:
            resultado.append(izquierda[i])
            i += 1
        else:
            resultado.append(derecha[j])
            j += 1
    resultado.extend(izquierda[i:])
    resultado.extend(derecha[j:])
    return resultado

Aquí, la mejora en el tiempo de ejecución se logra mediante el uso de espacio extra para almacenar las sublistas. Este es un claro ejemplo del trade-off entre tiempo y espacio: reducir el tiempo implica aumentar el espacio usado.

Otro caso a considerar es en algoritmos de búsqueda. La búsqueda en tablas hash ofrece una complejidad temporal promedio de O(1), pero requiere espacio adicional para almacenar la estructura hash. En contraste, la búsqueda secuencial tiene una complejidad de O(n) y no necesita espacio extra.

En Python, una implementación simplificada de una tabla hash podría ser:

def busqueda_hash(lista, clave_busqueda):
    tabla_hash = {}
    for elemento in lista:
        tabla_hash[elemento] = True
    if clave_busqueda in tabla_hash:
        print("Elemento encontrado.")
    else:
        print("Elemento no encontrado.")

Utilizar una tabla hash mejora el tiempo de búsqueda, pero aumenta el espacio utilizado. Este es un compromiso aceptable cuando se prioriza la velocidad de acceso, especialmente en conjuntos de datos grandes.

Es importante también considerar el consumo de memoria en algoritmos recursivos. La recursividad puede llevar a un mayor uso de la pila de llamadas, lo que implica más espacio. Por ejemplo, el cálculo del factorial de un número en Python:

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n - 1)

Este enfoque recursivo es elegante pero puede provocar un desbordamiento de pila con valores grandes de n. Una alternativa es utilizar una implementación iterativa, que reduce el consumo de memoria. En Python:

def factorial_iterativo(n):
    resultado = 1
    for i in range(1, n + 1):
        resultado *= i
    return resultado

Al preferir la versión iterativa, sacrificamos la simplicidad del código recursivo por un uso más eficiente de la memoria.

En resumen, al diseñar algoritmos es esencial evaluar el impacto en tiempo y espacio. Algunas preguntas clave que debemos hacernos son:

• ¿Es más crítico reducir el tiempo de ejecución o el uso de memoria en este contexto?
• ¿Podemos aceptar un mayor consumo de memoria para acelerar el algoritmo?
• ¿Existen límites de hardware que impongan restricciones en el espacio disponible?

Tomando decisiones informadas sobre estos aspectos, crearemos soluciones más adecuadas y eficientes para los problemas que enfrentamos.

Técnicas de optimización y trade-offs en diseño de algoritmos

La optimización de algoritmos es esencial para mejorar la eficiencia y rendimiento de los programas. Al diseñar algoritmos, es importante considerar diversas técnicas de optimización que pueden reducir el tiempo de ejecución o el uso de memoria. Sin embargo, es fundamental entender que mejorar un aspecto puede implicar sacrificios en otro, lo que se conoce como trade-offs en el diseño de algoritmos.

Una técnica común es seleccionar el algoritmo más adecuado según las características del problema y los datos. Por ejemplo, si sabemos que la lista a ordenar está casi ordenada, el ordenamiento por inserción puede ser más eficiente que otros algoritmos:

Algoritmo OrdenamientoInsercionOptimizado
    // Definir un tamaño máximo para el arreglo
    Definir MAX_SIZE Como Entero
    MAX_SIZE <- 100
    
    // Declarar el arreglo con un tamaño fijo
    Dimension lista[MAX_SIZE]
    
    // Declarar variables
    Definir n, i, j, valorActual Como Entero
    Definir optimizado Como Logico
    
    // Leer el número de elementos
    Escribir "Ingrese el número de elementos (máximo ", MAX_SIZE, "):"
    Leer n
    
    // Validar que n no exceda el tamaño máximo
    Si n > MAX_SIZE Entonces
        Escribir "El número de elementos excede el tamaño máximo permitido de ", MAX_SIZE, "."
    Fin Si

    // Leer los elementos de la lista
    Para i <- 1 Hasta n Hacer
        Escribir "Ingrese el elemento ", i, ":"
        Leer lista[i]
    Fin Para

    // Implementar el Ordenamiento por Inserción Optimizado
    Para i <- 2 Hasta n Hacer
        valorActual <- lista[i]
        j <- i - 1
        optimizado <- Verdadero  // Asumimos que la lista ya está ordenada
        
        Mientras j > 0 Y lista[j] > valorActual Hacer
            lista[j + 1] <- lista[j]
            j <- j - 1
            optimizado <- Falso  // Detectamos una desordenación
        Fin Mientras
        
        lista[j + 1] <- valorActual
        
        // Si no se realizaron desordenaciones, la lista ya está ordenada
        Si optimizado Entonces
            Fin Si
        Fin Para
        
        // Mostrar la lista ordenada
        Escribir "La lista ordenada es:"
        Para i <- 1 Hasta n Hacer
            Escribir lista[i]
        Fin Para
Fin Algoritmo

En Python, el código equivalente es:

def ordenamiento_insercion_optimizado(lista):
    for i in range(1, len(lista)):
        valor_actual = lista[i]
        j = i - 1
        while j >= 0 and lista[j] > valor_actual:
            lista[j + 1] = lista[j]
            j -= 1
        lista[j + 1] = valor_actual

Otra técnica es el uso de estructuras de datos apropiadas para mejorar la eficiencia. Por ejemplo, utilizar un diccionario o tabla hash para acelerar búsquedas. El código en Python es:

def busqueda_con_hash(lista, objetivo):
    tabla_hash = {elemento: True for elemento in lista}
    if objetivo in tabla_hash:
        print("Elemento encontrado.")
    else:
        print("Elemento no encontrado.")

Esta estrategia mejora el tiempo de búsqueda a costa de aumentar el espacio de memoria utilizado.

La optimización de bucles es otra técnica efectiva. Evitar cálculos redundantes dentro de bucles puede reducir significativamente el tiempo de ejecución. Por ejemplo, calcular previamente el tamaño de una lista:

Algoritmo SumarElementos
    // Definir un tamaño máximo para el arreglo
    Definir MAX_SIZE Como Entero
    MAX_SIZE <- 100  // Puedes ajustar este valor según tus necesidades
    
    // Declarar el arreglo con un tamaño fijo
    Dimension lista[MAX_SIZE]
    
    // Declarar variables
    Definir n, i, suma Como Entero
    
    // Inicializar la suma
    suma <- 0
    
    // Leer el número de elementos
    Escribir "Ingrese el número de elementos (máximo ", MAX_SIZE, "):"
    Leer n
    
    // Validar que n no exceda el tamaño máximo
    Si n > MAX_SIZE Entonces
        Escribir "El número de elementos excede el tamaño máximo permitido de ", MAX_SIZE, "."
    Fin Si

    // Leer los elementos de la lista
    Para i <- 1 Hasta n Hacer
        Escribir "Ingrese el elemento ", i, ":"
        Leer lista[i]
    Fin Para

    // Sumar los elementos
    Para i <- 1 Hasta n Hacer
        suma <- suma + lista[i]
    Fin Para

    // Mostrar la suma
    Escribir "La suma es: ", suma
Fin Algoritmo

En Python:

def sumar_elementos(lista):
    tamaño = len(lista)
    suma = 0
    for i in range(tamaño):
        suma += lista[i]
    print(f"La suma es: {suma}")

Además, implementar algoritmos in-place puede reducir el uso de memoria al modificar los datos directamente sin necesidad de estructuras auxiliares. Un ejemplo es el ordenamiento rápido optimizado. En Python:

def ordenamiento_rapido_in_place(lista):
    def quicksort(lista, inicio, fin):
        if inicio < fin:
            pivote = particionar(lista, inicio, fin)
            quicksort(lista, inicio, pivote - 1)
            quicksort(lista, pivote + 1, fin)

    def particionar(lista, inicio, fin):
        pivote = lista[fin]
        i = inicio - 1
        for j in range(inicio, fin):
            if lista[j] <= pivote:
                i += 1
                lista[i], lista[j] = lista[j], lista[i]
        lista[i + 1], lista[fin] = lista[fin], lista[i + 1]
        return i + 1

    quicksort(lista, 0, len(lista) - 1)

Al modificar la lista original, evitamos usar memoria adicional, pero debemos tener cuidado con efectos secundarios si otros procesos dependen de los datos originales.

La memoización es una técnica que almacena los resultados de cálculos costosos para evitar recomputarlos. Esto es especialmente útil en algoritmos recursivos como el cálculo de números de Fibonacci.

En Python:

def fibonacci_memoizado(n, memo={}):
    if n in memo:
        return memo[n]
    if n == 0 or n == 1:
        memo[n] = n
    else:
        memo[n] = fibonacci_memoizado(n - 1, memo) + fibonacci_memoizado(n - 2, memo)
    return memo[n]

n = int(input("Ingrese un número: "))
resultado = fibonacci_memoizado(n)
print(f"El Fibonacci de {n} es: {resultado}")

La memoización mejora el tiempo de ejecución a cambio de utilizar más espacio en memoria para almacenar los resultados intermedios.

Considerar trade-offs es crucial al diseñar algoritmos. Por ejemplo, al paralelizar un algoritmo, podemos reducir el tiempo de ejecución en sistemas multicore, pero aumentamos la complejidad y posibilidad de errores por concurrencia.

Otro trade-off común es entre la precisión y la eficiencia. En algunos casos, utilizar algoritmos aproximados puede ser aceptable si el aumento en velocidad compensa la pequeña pérdida de exactitud.

Por ejemplo, el algoritmo de ordenamiento Timsort, utilizado en Python, combina ordenamiento por inserción y merge sort para aprovechar las sublistas ya ordenadas y optimizar el rendimiento en casos reales.