Sort List Merge Sort

Implement merge sort on a list of integers and return a new sorted list.

merge sort sorting recursion

Implement the function `merge_sort(arr)` that takes a list of integers `arr` and returns a new list containing the same integers in non-decreasing order. You must use the merge sort algorithm: recursively split the list into halves, sort each half, and merge the sorted halves. Your solution must not modify the input list and must not use built-in sorting functions like `sorted()` or `.sort()`.

Function signature: `def merge_sort(arr: list) -> list:`

Constraints

Input list length: 0 <= len(arr) <= 1000. Each element is an integer. The algorithm should run in O(n log n) time and O(n) extra space.

Example

>>> merge_sort([3, 1, 2])
[1, 2, 3]
>>> merge_sort([5, 4, 3, 2, 1])
[1, 2, 3, 4, 5]
>>> merge_sort([])
[]

10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Base case: if the list has 0 or 1 element, it is already sorted.

Split the list into two halves using `len(arr) // 2`.

Write a helper function to merge two sorted lists into one sorted list.

Be careful not to modify the original input; create new lists during merging.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.