Python Merge Sort

Merge sort is a classic divide-and-conquer sorting algorithm: it splits a list in half over and over until each piece has just one element, then merges those pieces back together in sorted order. Unlike simpler algorithms such as bubble sort or insertion sort, merge sort guarantees O(n log n) performance no matter how the input is arranged, which makes it a favorite for teaching algorithmic thinking and for real-world use when predictable performance and stability matter.

How Merge Sort Works

Merge sort rests on a simple insight: a list of zero or one elements is already sorted, and two already-sorted lists can be combined into one sorted list very cheaply by repeatedly comparing their front elements. The algorithm has two phases that happen together through recursion:

Divide: the list is split at its midpoint into a left half and a right half. Each half is then recursively split again, and again, until every sublist contains at most one element. Because slicing a Python list (arr[:mid]) creates a brand-new list object with copied references to the original items, each recursive call works on its own independent list — the original list passed in is never mutated by the recursive calls themselves.

Conquer (merge): once the recursion bottoms out at single-element (or empty) lists, the algorithm starts combining pairs of sorted lists into larger sorted lists. This combining step, called the merge, walks two sorted lists with two pointers, always taking the smaller of the two current front elements and appending it to a new result list. Because both inputs to a merge are already sorted, this comparison-and-append process only needs a single pass through each list, giving the merge step O(n) time for n total elements at that level.

Stacking the levels together: there are log₂n levels of splitting (since the list halves each time), and each level does O(n) total work across all the merges at that level. Multiply those together and you get the well-known O(n log n) time complexity, which holds for the best, average, and worst case — merge sort’s performance does not degrade on already-sorted or reverse-sorted input the way quicksort’s can.

The trade-off is space: because each merge builds a brand-new list rather than rearranging elements in place, merge sort as normally implemented uses O(n) extra memory. It is also stable: if two elements are considered equal by the comparison, their relative order from the original list is preserved, because the merge step always prefers the left list when the two front elements are equal.

Syntax

Merge sort in Python usually takes the shape of two cooperating functions: one that recurses and divides, and one that merges two sorted lists.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

Part	Purpose
if len(arr) <= 1: return arr	Base case — a list with 0 or 1 elements is already sorted; this stops the recursion.
mid = len(arr) // 2	Finds the midpoint using integer (floor) division so the split works for both even and odd lengths.
merge_sort(arr[:mid]) / merge_sort(arr[mid:])	Recursively sorts each half independently.
merge(left, right)	Combines two already-sorted lists into one sorted list.
left[i] <= right[j]	The comparison that decides which element goes next; using <= instead of < keeps the sort stable.
result.extend(left[i:])	Appends whatever is left over once one side runs out — only one of the two extend calls ever adds anything.

Examples

Example 1: Sorting a list of numbers

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

numbers = [38, 27, 43, 3, 9, 82, 10]
sorted_numbers = merge_sort(numbers)
print(sorted_numbers)

Output:

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

Notice that merge_sort returns a brand-new list; the original numbers list is left untouched. This is a direct consequence of using slicing and building fresh lists in merge rather than sorting in place.

Example 2: Watching the recursion happen

To really see the divide-and-conquer structure, this version prints every split and every merge, indented by recursion depth.

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

def merge_sort_verbose(arr, depth=0):
    indent = "  " * depth
    print(f"{indent}Splitting: {arr}")
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort_verbose(arr[:mid], depth + 1)
    right = merge_sort_verbose(arr[mid:], depth + 1)
    merged = merge(left, right)
    print(f"{indent}Merged:   {merged}")
    return merged

merge_sort_verbose([5, 2, 4, 1])

Output:

Splitting: [5, 2, 4, 1]
  Splitting: [5, 2]
    Splitting: [5]
    Splitting: [2]
  Merged:   [2, 5]
  Splitting: [4, 1]
    Splitting: [4]
    Splitting: [1]
  Merged:   [1, 4]
Merged:   [1, 2, 4, 5]

Reading top to bottom, the list is split all the way down to single elements first (the recursive calls happen before any merging can occur), and only then do the merges start bubbling back up, combining pairs into larger and larger sorted runs until the whole list is sorted.

Example 3: Sorting objects by a key, and stability in action

from dataclasses import dataclass

@dataclass
class Student:
    name: str
    score: int

def merge_sort_by_key(items, key):
    if len(items) <= 1:
        return items
    mid = len(items) // 2
    left = merge_sort_by_key(items[:mid], key)
    right = merge_sort_by_key(items[mid:], key)
    return merge_by_key(left, right, key)

def merge_by_key(left, right, key):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if key(left[i]) <= key(right[j]):
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

students = [
    Student("Alice", 85),
    Student("Bob", 72),
    Student("Charlie", 85),
    Student("Dana", 90),
]

ranked = merge_sort_by_key(students, key=lambda s: -s.score)
for student in ranked:
    print(f"{student.name}: {student.score}")

Output:

Dana: 90
Alice: 85
Charlie: 85
Bob: 72

Alice and Charlie are tied at 85, and because merge sort is stable, Alice (who appeared first in the original list) still appears before Charlie in the result. A sorting algorithm that isn’t stable could easily have swapped their order, which matters a great deal when you sort by one key (score) after already having sorted or arranged data by another.

Under the Hood: Step by Step

Walking through merge_sort([5, 2, 4, 1]) from Example 2 makes the mechanics concrete:

• The call starts with [5, 2, 4, 1]. Since its length is greater than 1, it splits into [5, 2] and [4, 1] and recurses on each.
• [5, 2] splits into [5] and [2], both of which hit the base case and return immediately. Merging them compares 5 and 2, takes 2 first, then appends the leftover 5, giving [2, 5].
• [4, 1] splits into [4] and [1], which merge into [1, 4] the same way.
• Finally, the two sorted halves [2, 5] and [1, 4] are merged: compare 2 and 1 (take 1), compare 2 and 4 (take 2), compare 5 and 4 (take 4), then append the leftover 5 — producing [1, 2, 4, 5].

Every merge only ever looks at the current front of each list, which is exactly why both inputs to a merge must already be sorted — the algorithm never looks further ahead than that.

Common Mistakes

Mistake 1: Using < instead of <= in the merge comparison. Writing if left[i] < right[j]: instead of <= still produces a correctly sorted list, but it silently breaks stability: when elements are equal, the element from the right sublist can end up chosen first, reversing the original relative order of equal items. Always use <= (or, for descending sort, >=) when you want to preserve stability.

Mistake 2: Forgetting to extend both leftover lists. A common bug is writing only result.extend(left[i:]) and forgetting result.extend(right[j:]) (or vice versa). Since the main while loop stops as soon as either list is exhausted, whichever list still has elements remaining needs to have the rest of its (already sorted) items appended — skipping one of these lines silently drops elements from the final result.

Mistake 3: Assuming merge sort is in-place like quicksort. Because the standard implementation builds new lists at every merge, it uses O(n) additional memory, not O(1). If you need an in-place sort with O(1) auxiliary space, merge sort’s straightforward form is not the right tool; Timsort (Python’s built-in sorted() and list.sort()) is a more sophisticated hybrid that manages memory far more efficiently while still being stable.

Best Practices

• In real production code, prefer Python’s built-in sorted() or list.sort() — both use Timsort, which is stable, highly optimized in C, and adapts to existing order in the data. Implement merge sort yourself for learning, interviews, or when you need a custom merge behavior that sorted() can’t express.
• Keep the merge helper function separate from the recursive merge_sort function; it keeps each function focused and makes the merge logic easy to test on its own with hand-picked sorted lists.
• Use <= in the comparison so your implementation is stable, matching the behavior Python programmers expect from sorted().
• Add type hints (e.g. def merge_sort(arr: list[int]) -> list[int]:) to make the expected input and output explicit, especially in shared or library code.
• For very large datasets where memory is tight, look into iterative (bottom-up) merge sort or external merge sort variants that avoid deep recursion and reduce peak memory use.
• Avoid needless copying: if you only need to know whether a list is sorted, or you can sort in place with list.sort(), don’t reach for a recursive merge sort that allocates many intermediate lists.

Practice Exercises

• Exercise 1: Modify the merge function so that it sorts in descending order instead of ascending order, without changing merge_sort. Test it on [4, 1, 3, 9, 2] and check the result is [9, 4, 3, 2, 1].
• Exercise 2: Write a function count_merge_calls(arr) that runs a merge sort and counts how many times the merge function is called in total for a list of length n. Compare the count for lists of length 4, 8, and 16 — how does it relate to n?
• Exercise 3: Adapt merge_sort_by_key from Example 3 to sort a list of (word, length) tuples by word length, breaking ties by keeping the original order. Verify with a small list that includes at least two words of equal length.

Summary

• Merge sort is a divide-and-conquer algorithm: split the list in half recursively until pieces have 0 or 1 elements, then merge sorted pieces back together.
• The merge step combines two sorted lists in O(n) time using two pointers, always taking the smaller current front element.
• Overall time complexity is O(n log n) in the best, average, and worst case — unlike quicksort, its performance doesn’t degrade on adversarial input.
• Space complexity is O(n) because each merge builds new lists rather than sorting in place.
• Merge sort is stable when the comparison uses <=, meaning equal elements keep their original relative order.
• In practice, use Python’s built-in sorted()/list.sort() (Timsort) for real work; implement merge sort yourself to understand the algorithm or when you need custom merge semantics.