Сортировки слиянием

"""
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=",")

def merge_sort(A):
    if len(A) <=1:
        return
    middle = len(A)//2
    L=[A[i] for i in range(0,middle)]
    R= [A[i] for i in range(middle, len(A))]
    merge_sort(L)
    merge_sort(R)
    C = merge(L,R)
 
B = [5,2,7,3,1]
merge_sort(B)
print(*B)

def merge (A:list, B:list):
    C = [0] * (len(A)+len(B))
    i=k=n=0
    while i < len(A) and k < len(B):
        if A[i]<=B[k]:
            C[n] = A[i]; i+=1; n+=1
        else:
            C[n] = B[k]; k+=1; n+=1
    while i < len(A):
        C[n] = A[i]; i+=1; n+=1
    while k < len(B):
        C[n] = B[k]; k+=1; n+=1
    return C
 
 
A = [x for x in range(1,13,2)]
B = [y for y in range (2, 14,2)]
print(A)
print(B)
print(merge(A,B))

# New indexing function that includes the right index.
def get_partial_list(origin_list, left_index, right_index): # Added
    return origin_list[left_index:right_index+1]
 
 
def MERGE(A,start,mid,end):
    L = get_partial_list(A,start,mid)
    R = get_partial_list(A,mid+1,end)
    i = 0
    j = 0
    k = start
    for l in range(k,end+1):            # changed
        if j >= len(R) or (i < len(L) and L[i] < R[j]):
            A[l] = L[i]
            i = i + 1
        else:
            A[l] = R[j]
            j = j + 1  
 
def mergeSort(A,p,r):
    if r - p > 0:                          # changed
        mid = int((p+r)/2)
        mergeSort(A,p,mid)
        mergeSort(A,mid+1,r)             # changed
        MERGE(A,p,mid,r)
 
A  = [20, 30, 21, 15, 42, 45, 31, 0, 9]
mergeSort(A,0,len(A)-1)                 # changed
print A

def merge_sort(A):
    if len(A) <=1:
        return
    middle = len(A)//2
    L=[A[i] for i in range(0,middle)]
    R= [A[i] for i in range(middle, len(A))]
    merge_sort(L)
    merge_sort(R)
    C = merge(L,R)
 
B = [5,2,7,3,1]
merge_sort(B)
print(*B)

def merge_sort(alist, start, end):
    '''Sorts the list from indexes start to end - 1 inclusive.'''
    if end - start > 1:
        mid = (start + end)//2
        merge_sort(alist, start, mid)
        merge_sort(alist, mid, end)
        merge_list(alist, start, mid, end)
 
def merge_list(alist, start, mid, end):
    left = alist[start:mid]
    right = alist[mid:end]
    k = start
    i = 0
    j = 0
    while (start + i < mid and mid + j < end):
        if (left[i] <= right[j]):
            alist[k] = left[i]
            i = i + 1
        else:
            alist[k] = right[j]
            j = j + 1
        k = k + 1
    if start + i < mid:
        while k < end:
            alist[k] = left[i]
            i = i + 1
            k = k + 1
    else:
        while k < end:
            alist[k] = right[j]
            j = j + 1
            k = k + 1
 
size = int(input()) 
alist = input().split()
alist = [int(x) for x in alist]
merge_sort(alist, 0, len(alist))
print(*alist)