Merge Sort

Implement the classic divide-and-conquer merge sort algorithm.

sorting recursion divide-and-conquer

Write a function `merge_sort(numbers)` that takes a list of numbers and returns a new list containing the same elements sorted in ascending order. The function must implement the merge sort algorithm: divide the list into halves, recursively sort each half, and merge the sorted halves. The input list must not be modified. Use recursion and ensure that `merge_sort` is a pure function (no side effects).

Constraints

Input length n satisfies 0 <= n <= 10^5. Elements are integers or floats. The algorithm must have O(n log n) time complexity and O(n) auxiliary space complexity.

Example

>>> merge_sort([3, 1, 4, 1, 5])
[1, 1, 3, 4, 5]
>>> merge_sort([9, 8, 7])
[7, 8, 9]
>>> merge_sort([])
[]

30 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Base case: a list of length 0 or 1 is already sorted.

Split the list into two halves using integer division.

Merge two sorted lists by comparing the front elements and collecting the smaller one.

Use a slice to copy the merged result without modifying the input list.

Test Results

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