Merge Sort combinado con Insertion Sort

Un algoritmo muy usado en ordenamiento es el merge sort como vimos en la clase de este curso. En la práctica ese método se combina con el insertion sort porque el insertion sort aunque es ineficiente con listas grandes es muy eficiente con listas pequeñas por ejemplo de 10 elementos.

Este código combina los dos algoritmos que vimos en clase. El punto donde se combinan es aquí

if n <= INSERT_SORT_THRESHOLD:
        return insert_sort(list)

la variable INSERT_SORT_THRESHOLD indica cuantos elementos debe tener la lista para iniciar un insertion sort. Un valor de cero indica que siempre usar merge sort

INSERT_SORT_THRESHOLD = 10

def insert_sort(list):
    n = len(list)
    if n == 0:
        return list
    for i in range(1, n):        
        itm = list[i]
        index = i
        #move from i-1 to 0                
        for j in range(i - 1, -1, -1):
            if itm < list[j] :
                index = j
                list[j+1] = list[j]
            else:
                break
        list[index] = itm        
    return list

def merge_sort(list):
    n = len(list)
    if n <= 1:
        return list

    if n <= INSERT_SORT_THRESHOLD:
        return insert_sort(list)

    middle = n // 2
    left = merge_sort(list[:middle])
    right = merge_sort(list[middle:])

    left_c = 0
    right_c = 0
    k = 0

    while left_c < len(left) and right_c < len(right):
        if left[left_c] < right[right_c]:
            list[k] = left[left_c]
            left_c += 1
        else:
            list[k] = right[right_c]
            right_c += 1
        k += 1

    while left_c < len(left):
        list[k] = left[left_c]
        k += 1
    
    while right_c < len(right):
        list[k] = right[right_c]
        k += 1

    return list

import random
random_list = [random.randint(0, 1000) for x in range(0, 20)]
print(random_list)
print('-' * 20)
print(insert_sort(random_list))