from typing import TypeVar
import unittest

T = TypeVar("T")


def merge_sort(items: list[T]) -> list[T]:
    """Return a new list containing the items in sorted order."""
    if len(items) <= 1:
        return items.copy()

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


def _merge(left: list[T], right: list[T]) -> list[T]:
    """Merge two sorted lists."""
    merged: list[T] = []
    left_index = right_index = 0

    while left_index < len(left) and right_index < len(right):
        if left[left_index] <= right[right_index]:  # Preserve stable ordering.
            merged.append(left[left_index])
            left_index += 1
        else:
            merged.append(right[right_index])
            right_index += 1

    merged.extend(left[left_index:])
    merged.extend(right[right_index:])
    return merged


class MergeSortTests(unittest.TestCase):
    def test_unsorted_integers(self) -> None:
        self.assertEqual(merge_sort([5, 2, 8, 1, 3]), [1, 2, 3, 5, 8])

    def test_empty_and_single_item_lists(self) -> None:
        self.assertEqual(merge_sort([]), [])
        self.assertEqual(merge_sort(["only"]), ["only"])

    def test_duplicates(self) -> None:
        self.assertEqual(merge_sort([3, 1, 3, 2, 1]), [1, 1, 2, 3, 3])


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