MergeSort

📖

Este es un algoritmo de ordenación el cual sigue el esquema de Divide y Vencerás

En este algoritmo, la ordenación sucede en el momento de la combinación, los arrays se recorren a la vez

ℹ️

Sabiendo que los sub-arrays que han devuelto las llamadas recursivas estan ordenados, entonces ahora los combinaremos de la siguiente manera:

Se compara el valor más pequeños de en la primera posición de los sub-arrays

El menor se saca del array y se coloca en un nuevo array

Se repite este paso hasta que todos los sub-arrays estan vacios

from random import randint

def merge_sort(arr):
    # Base case
    if len(arr) == 1:
        return arr
    # Recursive case
    else:
        # Divide the array in two halves
        m = len(arr) // 2
        left = arr[:m]
        right = arr[m:]
        # Recursive call
        left = merge_sort(left)
        right = merge_sort(right)
        # Merge the two halves
        return merge(left, right)

def merge(left, right):
    # Initialize the merged array
    merged = []
    # Initialize the pointers
    i = 0
    j = 0
    
    # Merge the two halves
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
            
    # Append the remaining elements
    while i < len(left):
        merged.append(left[i])
        i += 1
    while j < len(right):
        merged.append(right[j])
        j += 1
    return merged

if __name__ == "__main__":
    n = 1000
    # Generate a random sorted array
    arr = [randint(0, 100) for _ in range(n)]
    
    res1 = merge_sort(arr)
    print(res1)