Merge Sort

Write merge_sort(values: list[int]) -> list[int] that returns a new sorted list: a list of one element or none is already sorted and is returned as it is; otherwise cut the list at mid = len(values) // 2 into the slices values[:mid] and values[mid:], sort each half by calling merge_sort on it, and combine the two sorted halves with a helper merge(left, right) that you also write: two indexes i and j walk the halves, the smaller value is appended to merged each time (the left one when they are equal) and the leftover slices left[i:] and right[j:] are added at the end. Merge sort is O(n log n) in every case. Do NOT write a main block or any top-level test code; the tests construct the calls. Input: one line of space-separated integers (possibly empty); the tests print the list your function returns.