Merge sort algorithm.

MergeSort.py

# Despues de revisar https://binary-coffee.dev/post/conociendo-el-ordenamiento-por-mezcla-merge-sort
# me animé a implementarlo en Python. 

def MergeTwoOrderedLists(A, B):
    """
        Merge two ordered lists.

        :param A: a ordered collection with heterogeneous
        comparable items with items in collection B
        :param B: a ordered collection with heterogeneous
        comparable items with items in collection A
        :return: an array with all items in A and B ordered
        
        Examples:
        >>> MergeTwoOrderedLists([2, 4, 7], [1, 3, 5, 6])
        [1, 2, 3, 4, 5, 6, 7]
        >>> MergeTwoOrderedLists([], [1])
        [1]
        >>> MergeTwoOrderedLists([2], [1])
        [1, 2]
    """
    i = j = 0
    total = len(A) + len(B)
    result = []
    while len(result) < total:
        if i == len(A):
            result.append(B[j])
            j += 1
        elif j == len(B):
            result.append(A[i])
            i += 1
        elif i < len(A) and j < len(B) and A[i] < B[j]:
            result.append(A[i])
            i += 1
        elif j < len(B):
            result.append(B[j])
            j += 1
    return result

def MergeSort(A):
    """
        Merge sort algorithm.

        :param A: a collection with heterogeneous comparable items inside
        :return: another collection ordered by ascending

        Examples:
        >>> MergeSort([0, 5, 3, 2, 2])
        [0, 2, 2, 3, 5]
        >>> MergeSort([])
        []
        >>> MergeSort([-2, -5, -45])
        [-45, -5, -2]
    """
    if len(A) < 2:
        return list(A[: ])
    middle = len(A) // 2
    left = MergeSort(A[: middle])
    right = MergeSort(A[middle: ])
    result = MergeTwoOrderedLists(left, right)
    return result


# Some tests:
assert MergeSort([]) == []

assert MergeSort(['A']) == ['A']

assert MergeSort(['B', 'A']) == ['A', 'B']

assert MergeSort([4,3,2,1]) == list(range(1, 5))

assert MergeSort([6, 2, 5, 1, 3, 4]) == list(range(1, 7))

a1000_501_1_500 = list(range(1000, 500, -1)) + list(range(1, 501))

assert MergeSort(a1000_501_1_500) == list(range(1, 1001))