from __future__ import annotations

import unittest
from typing import Protocol, Sequence, TypeVar


class Comparable(Protocol):
    def __lt__(self, other: object, /) -> bool:
        ...


T = TypeVar("T", bound=Comparable)


def merge(left: Sequence[T], right: Sequence[T]) -> list[T]:
    """Merge two sorted sequences into one sorted list."""
    result: list[T] = []
    i = 0
    j = 0

    while i < len(left) and j < len(right):
        # Prefer the left item on ties to keep the sort stable.
        if right[j] < left[i]:
            result.append(right[j])
            j += 1
        else:
            result.append(left[i])
            i += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result


def merge_sort(items: Sequence[T]) -> list[T]:
    """Return a sorted copy of items using merge sort."""
    if len(items) <= 1:
        return list(items)

    midpoint = len(items) // 2
    left = merge_sort(items[:midpoint])
    right = merge_sort(items[midpoint:])
    return merge(left, right)


class TestMergeSort(unittest.TestCase):
    def test_sorts_numbers(self) -> None:
        self.assertEqual(merge_sort([5, 2, 9, 1, 5, 6]), [1, 2, 5, 5, 6, 9])

    def test_handles_empty_and_single_item(self) -> None:
        self.assertEqual(merge_sort([]), [])
        self.assertEqual(merge_sort([42]), [42])

    def test_does_not_mutate_input(self) -> None:
        values = [3, -1, 0, -1]
        self.assertEqual(merge_sort(values), [-1, -1, 0, 3])
        self.assertEqual(values, [3, -1, 0, -1])


if __name__ == "__main__":
    unittest.main()