Сортировки - Python

Алгоритмы сортировок на Python.

Сортировка вставками.

def insert_sort(arr):
    for i in range(len(arr)):
        value = arr[i]
        j = i
        while j and value < arr[j - 1]:
            arr[j] = arr[j - 1]
            j -= 1
        arr[j] = value
            
arr = [1, 4, 5, 0, 8, 9, 1, 9, 2, 11, 0, 9]
answer = [1, 4, 5, 0, 8, 9, 1, 9, 2, 11, 0, 9]
answer.sort()
insert_sort(arr)
assert arr == answer 

Быстрая сортировка.

def quick_sort(nums):
    if not nums:
        return []
    
    left = []
    right = []
    pivot = nums[0]
    
    for i in range(1, len(nums)):
        if nums[i] < pivot:
            left.append(nums[i])
        else:
            right.append(nums[i])
    
    return quick_sort(left) + [pivot] + quick_sort(right)


arr = [1, 4, 5, 0, 8, 9, 1, 9, 2, 11, 0, 9]
answer = [1, 4, 5, 0, 8, 9, 1, 9, 2, 11, 0, 9]
answer.sort()
assert quick_sort(arr) == answer

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

def merge_sort(arr):
    if len(arr) > 1:
        left = arr[len(arr) // 2:]
        right = arr[:len(arr) // 2]
        merge_sort(left)
        merge_sort(right)

        i, j, k = 0, 0, 0
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                arr[k] = left[i]
                i += 1
            else:
                arr[k] = right[j]
                j += 1
            k += 1

        while i < len(left):
            arr[k] = left[i]
            i += 1
            k += 1

        while j < len(right):
            arr[k] = right[j]
            j += 1
            k += 1
            
            
arr = [1, 4, 5, 0, 8, 9, 1, 9, 2, 11, 0, 9]
answer = [1, 4, 5, 0, 8, 9, 1, 9, 2, 11, 0, 9]
answer.sort()
merge_sort(arr)
assert arr == answer