Python · Course navigation

Python merge sort

Sort halves recursively and merge them in order.

On this page

Before you start

Recursion, slicing, and lists.

Sort halves recursively and merge them in order.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

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.

Code example

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]

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

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]

Behind the scenes

How Python processes this code

Python runs this source through its interpreter. It creates objects for values and resolves names as each statement runs.

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.