A minimal example of merge sort

merge_sort.py

from __future__ import annotations

import random
from typing import List


def merge_sort(arr: List[int]) -> List[int]:
    if len(arr) == 1 or len(arr) == 0:
        return arr
    mid = len(arr) // 2
    left, right = merge_sort(arr[:mid]), merge_sort(arr[mid:])
    new = [-1 for _ in range(len(arr))]
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            new[i + j] = left[i]
            i += 1
        else:
            new[i + j] = right[j]
            j += 1
    while i < len(left):
        new[i + j] = left[i]
        i += 1
    while j < len(right):
        new[i + j] = right[j]
        j += 1
    return new


def test_merge_sort() -> bool:
    for _ in range(random.randint(1, 10)):
        arr = [random.randint(0, 10) for _ in range(random.randint(10, 20))]
        if not all(x == y for x, y in zip(sorted(arr), merge_sort(arr))):
            return False
    return True


if __name__ == "__main__":
    print(f"test result = {test_merge_sort()}")