CodeUtility
Making your developer's life easier!
Python Algorithms

Merge Sort in Python

Split the list in half, sort each half recursively and merge them back: always O(n log n).

  • Intermediate
  • 2 min read
  • 1 runnable example
What you'll learn
  • Recursive splitting with slices
  • Merging two sorted lists
  • Time and memory cost
Run in the Python compiler →
merge_sort([38, 27, 43, 3]) step by step
  • [3, 27, 38, 43]merged
    • [27, 38]
      • [38]
      • [27]
    • [3, 43]
      • [43]
      • [3]
Split down to single values, then merge sorted pieces on the way back up.

Divide, then merge

Merge sort splits a list into smaller halves, sorts each half recursively, and merges the sorted results.

Key points

  1. A list of length 0 or 1 is already sorted: that is the base case.
  2. Merge two sorted lists by repeatedly taking the smaller front value.
  3. There are about log n levels of n work each: O(n log n).
  4. It needs O(n) extra memory for the merged lists.

When should you use it?

  • Practice problem solving and data structures.
  • Process data when every algorithm step must be explicit.
  • Prepare for programming exercises, exams, and interviews.

Merge Sort in Python visualizer

O(n log n)

Use Play or Step to follow each comparison and data movement.

Example code

Run code →
main.py
def merge_sort(values):
    if len(values) <= 1:
        return values
    middle = len(values) // 2
    left = merge_sort(values[:middle])
    right = merge_sort(values[middle:])
    result = []
    left_index = right_index = 0
    while left_index < len(left) and right_index < len(right):
        if left[left_index] <= right[right_index]:
            result.append(left[left_index])
            left_index += 1
        else:
            result.append(right[right_index])
            right_index += 1
    return result + left[left_index:] + right[right_index:]

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
Get a Run button for this example

Result of running the code

[3, 9, 10, 27, 38, 43, 82]

Code explanation

The recursion reaches lists of length one. Merging then rebuilds sorted lists from the bottom up. Time complexity is O(n log n).

Change the values and run the program in the CodeUtility online Python compiler without installing Python locally.

Practice exercises

Modify the runnable example with the exercises below to build understanding beyond copying the result.

  1. Try empty, single-item, and duplicate-value inputs.
  2. Print state after every step to observe the algorithm.
  3. Benchmark 100, 1,000, and 10,000 items, then compare another approach.
Run in the Python compiler →

Practice with a challenge

Use what this lesson covers to solve a real problem. Each challenge runs in your browser with instant tests and an AI review.

All challenges