The Algorithms logo
The Algorithms
Acerca deDonar

Mergesort

K
w
s
L
Y 54 más contribuidores
"""
This is a pure Python implementation of the merge sort algorithm
For doctests run following command:
python -m doctest -v merge_sort.py
or
python3 -m doctest -v merge_sort.py
For manual testing run:
python merge_sort.py
"""


def merge_sort(collection: list) -> list:
    """Pure implementation of the merge sort algorithm in Python
    :param collection: some mutable ordered collection with heterogeneous
    comparable items inside
    :return: the same collection ordered by ascending
    Examples:
    >>> merge_sort([0, 5, 3, 2, 2])
    [0, 2, 2, 3, 5]
    >>> merge_sort([])
    []
    >>> merge_sort([-2, -5, -45])
    [-45, -5, -2]
    """

    def merge(left: list, right: list) -> list:
        """merge left and right
        :param left: left collection
        :param right: right collection
        :return: merge result
        """

        def _merge():
            while left and right:
                yield (left if left[0] <= right[0] else right).pop(0)
            yield from left
            yield from right

        return list(_merge())

    if len(collection) <= 1:
        return collection
    mid = len(collection) // 2
    return merge(merge_sort(collection[:mid]), merge_sort(collection[mid:]))


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    user_input = input("Enter numbers separated by a comma:\n").strip()
    unsorted = [int(item) for item in user_input.split(",")]
    print(*merge_sort(unsorted), sep=",")
Acerca de este algoritmo

Declaración de problema

Dada una matriz de n elementos, escriba una función para ordenar la matriz

Enfoque

  • Encontrar un punto medio y dividir la matriz en mitades basadas en el punto medio
  • Llamar recursivamente a la función de ordenación de fusión para las dos mitades
  • Combinar las dos mitades ordenadas para obtener la matriz ordenada

Complejidad temporal

O(n log n)

Complejidad espacial

O(n)

Ejemplo

arr = [1, 3, 9, 5, 0, 2]  

Divida la matriz en dos mitades [1, 3, 9] y [5, 0, 2]

Vuelva a llamar a la función de ordenación de combinación de llamadas para estas dos mitades, lo que proporcionará mitades ordenadas
=> [1, 3, 9] & [0, 2, 5]

Ahora combine ambas mitades para obtener la matriz ordenada [0, 1, 2, 3, 5, 9]

Enlaces de la implementación del código

Explicación de vídeo

Un vídeo CS50 que explica el algoritmo de ordemaniento de fusión