Basic example
Input
arr = [3,1,4,1,5,9,2,6]
Output
[1, 1, 2, 3, 4, 5, 6, 9]
After merge sort, the list is sorted ascending.
Full lesson preview
Implement merge sort
Write a merge sort that sorts a list of integers in ascending order using divide and conquer.
Python practice18 minSearching & SortingIntermediateLast updated March 25, 2026
Problem statement
Given an unsorted list of integers, implement merge sort to return a new list containing the same integers in non-decreasing order. Do not use built-in sort functions; implement the divide-and-conquer merging approach.
Task
Implement merge sort with O(n log n) time and O(n) extra space and return a new sorted list.
Examples
Input format
One argument: arr (list of integers).
Output format
A list of integers sorted in non-decreasing order.
Constraints
Time complexity: O(n log n). Additional space: O(n). Handle empty lists and lists with duplicates.
Samples
Sample 1
Input
arr = [5,2,3,1]
Output
[1, 2, 3, 5]
Sorted ascending order returned.