Python merge sort

Sort halves recursively and merge them in order.

Python

def merge_sort(values):
    if len(values) <= 1:
        return values.copy()
    middle = len(values) // 2
    left = merge_sort(values[:middle])
    right = merge_sort(values[middle:])
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    return merged + left[i:] + right[j:]

print(merge_sort([4, 1, 3, 2]))
assert merge_sort([]) == []
assert merge_sort([2, 1, 2]) == [1, 2, 2]

Output

[1, 2, 3, 4]

Explanation

Merge sort divides a sequence until each part has at most one item, then combines sorted parts. Two indices track the next unconsumed value in each half.

When values tie, taking from the left first preserves stability. After one half is exhausted, the remaining suffix of the other half is already sorted.

Explore the dry run

Guided walkthroughReady

1def merge_sort(values):

2 if len(values) <= 1:

3 return values.copy()

4 middle = len(values) // 2

5 left = merge_sort(values[:middle])

6 right = merge_sort(values[middle:])

7 merged = []

8 i = j = 0

9 while i < len(left) and j < len(right):

10 if left[i] <= right[j]:

11 merged.append(left[i])

12 i += 1

13 else:

14 merged.append(right[j])

15 j += 1

16 return merged + left[i:] + right[j:]

18print(merge_sort([4, 1, 3, 2]))

19assert merge_sort([]) == []

20assert merge_sort([2, 1, 2]) == [1, 2, 2]

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
Split the four-element input.	`left input = [4, 1], right input = [3, 2]`	—
Recursive splitting reaches [4], [1], [3], and [2] in traversal order.	`left input = [4, 1], right input = [3, 2]`	—
The two size-two merges produce sorted halves.	`left = [1, 4], right = [2, 3]`	—
At the outer merge, take 1 before 2.	`merged = [1], i becomes 1`	—
Take 2, then 3, before 4.	`merged = [1, 2, 3], j becomes 2`	—
Append the remaining left suffix [4].	`return = [1, 2, 3, 4]`	—
Print the result.	`return = [1, 2, 3, 4]`	[1, 2, 3, 4]

Cost and common mistakes

O(n log n) time and O(n) peak auxiliary storage, plus O(log n) recursive frames.

A missing base case causes unbounded recursion.
This educational implementation allocates slices and merged lists; use built-in sorting for ordinary application code.

Try it yourself

Predict merge_sort([3, 3, -1]).

Reveal answer and reasoning

The result is [-1, 3, 3]; duplicates are preserved.

Python merge sort

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading