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

def merge(list1, list2):
    i = k = 0
    list_res = []
    while i < len(list1) and k < len(list2):
        if list1[i] <= list2[k]:
            list_res.append(list1[i])
            i += 1
        else:
            list_res.append(list2[k])
            k += 1
    while i < len(list1):
        list_res.append(list1[i])
        i += 1
    while k < len(list2):
        list_res.append(list2[k])
        k += 1
    return list_res
 
 
def sort(original_list: list):
    if len(original_list) <= 1:
        return
    middle = len(original_list) // 2
    left = original_list[:middle]
    right = original_list[middle:]
    print('left:', left, 'right:', right)
    sort(left)
    sort(right)
    temp_list = merge(left, right)
    print('temp_list:', temp_list)
    # original_list = list(temp_list[i] for i in range(len(original_list))) - почему оно так не работает?!
    for i in range(len(original_list)):                                  # - а так работает?!
        original_list[i] = temp_list[i]
    print('original_list:', original_list)
    return original_list
 
 
 
print(sort([5, 4, 3, 2]))

# -*- coding: utf-8 -*-
 
 
def merge(right: list, left: list, result: list):
    result.append((left if left[0] < right[0] else right).pop(0))
    return merge(right, left, result) if left and right else result + left + right
 
 
def merge_sort(collection: list):
    if len(collection) == 1:
        return collection
    return merge(merge_sort(collection[len(collection) // 2:]),
                 merge_sort(collection[:len(collection) // 2]), [])
 
 
print(merge_sort([3, 2, 5, 4, 1, 6, 0, 10, 15]))

def sort(original_list: list):
    if len(original_list) <= 1:
        return original_list
    middle = len(original_list) // 2
    left = original_list[:middle]
    right = original_list[middle:]
    print('left:', left, 'right:', right)
    temp_list = merge(sort(left), sort(right))
    print('temp_list:', temp_list)
    original_list = temp_list.copy()
    print('original_list:', original_list)
    return original_list

# -*- coding: utf-8 -*-
 
 
def create_list(original: list, iteration: int = 0) -> list:
    if len(original) > 10:                      # Если длина спика достигла 10, то
        return original                         #     Возвращаем список
    temp = original[:]                          # Создаем [КОПИЮ] списка
    temp.append(len(original))                  # Добавляем переменную
    trash = create_list(temp, iteration + 1)    # Вызываем функцию снова, передаем [КОПИЮ] списка и повторяем твою ошибку
    print(iteration, trash)
    return original                             # Вовращаем [ОРИГИНАЛ] списка
 
 
print(create_list([]))

left = mergesort(left)
right = mergesort(right)

if len(original_list) <= 1:
        return

original_list = list(temp_list[i] for i in range(len(original_list)))

# Слияние двух упорядоченных списков:
 
def merge(s1,s2):
    r=[]
    i,j=0,0
    while(True):
        if i>= len(s1):
            r+=s2[j:]
            break
        if j>= len(s2):
            r+=s1[i:]
            break
        if s1[i] < s2[j]:
            r+=[s1[i]]
            i+=1 
        else:
            r+=[s2[j]]
            j+=1
    return r
 
# собственно сортировка
    
def mergeSort(x):
    xx=[]    # превращаем каждый элемент в список
    for a in x:
        xx=xx+[[a]]
    while(True):
        k=len(xx)  # когда остался единственный список - конец
        if k==1:
            break
        yy=[]
        i=0
        j=1
        while(True): # строим списки пар, потом четверок и т.п.
            if i==k: 
                break
            if j==k:
                yy+=[xx[i]]
                break
            else:
                yy+=[merge(xx[i],xx[j])]
            i+=2
            j+=2
            
        xx=yy
    return xx[0]
 
z=mergeSort([1,2,3,1,2,3,1,2,3])
print(z)
 
z=mergeSort([1,3,-4,8,2,34])
print(z)