Merge Sort In-Place

Estaba dándole vueltas al problema de cómo implementar un Merge Sort que realmente sea in-place, ya que la mayoría de versiones que he visto utilizan un arreglo adicional para guardar los elementos temporalmente. Al final, el problema se reduce a cómo hacer una sub-rutina (merge) que una dos listas virtuales que están dentro de la misma estructura lineal, una después de la otra. 

Esta subrutina merge debería recibir por parámetro una referencia a la estructura, el índice donde empieza la primer lista, el índice donde empieza la segunda y el índice donde termina la segunda.

Pensándolo un poco más, el problema puede verse como el problema de ordenar una lista donde la primera mitad ya se encuentra ordenada. Como la idea es hacerlo in-place, se puede insertar los elementos de la segunda mitad, uno a uno, dentro de la primera mitad por medio de intercambios. Esto que se acaba de describir es básicamente para lo que es bueno el estimado Insertion Sort, procesar listas que se encuentran relativamente ordenadas. 

Si se adapta el Insertion Sort para que trabaje con la división de sublistas que hace el Merge Sort, estaríamos hablando de que el Merge Sort podemos verlo como una generalización del Insertion. Otra más, el Shell Sort ya es una.

Aquí dejo mi implementación en Python del Merge Sort in-place, utilizando el Insertion como método para unir dos sublistas ordenadas. La función principal recibe la lista a ordenar y se encarga de invocar a la función auxiliar los índices iniciales. La función auxiliar se encarga de aplicar la técnica divide y conquista por medio de recursión. La función merge no es recursiva y utiliza ciclos para implementar la idea descrita anteriormente.

def merge(L, first, mid, last):

    for it in range(mid, last + 1):

        i = it

        while i > first and L[i] < L[i - 1]:

            L[i], L[i - 1] = L[i - 1], L[i]

            i -= 1

def merge_sort_aux(L, first, last):

    if first == last:

        return

    mid = (first + last) // 2

    merge_sort_aux(L, first, mid)

    merge_sort_aux(L, mid + 1, last)

    merge(L, first, mid + 1, last)

    

def merge_sort_inplace(L):

    if type(L) != list:

        raise Exception("L debe ser lista.")

    return merge_sort_aux(L, 0, len(L) - 1)