Python Merge Sort: Syntax, Usage, and Examples

Merge sort is a popular and efficient divide-and-conquer algorithm. In Python, merge sort works by recursively breaking a list into smaller halves, sorting each half, and then merging the sorted halves into a fully sorted list. It's known for its consistent performance, making it a strong choice when you need a reliable and stable sorting algorithm.

When you implement merge sort Python style, you're working with a clear and structured recursive pattern. This helps you not only understand the algorithm but also improve your recursion and problem-solving skills.

How Merge Sort Works in Python

Merge sort follows these steps:

1. Split the unsorted list into two halves.
2. Recursively sort each half using merge sort.
3. Merge the two sorted halves into a single sorted list.

This process continues until the list is reduced to single-element lists, which are naturally sorted. At that point, you’ve reached the base case, and the algorithm can start combining results.

Here’s a simple version of the merge sort algorithm Python supports using lists:

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])

    return merge(left_half, right_half)

def merge(left, right):
    sorted_list = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            sorted_list.append(left[i])
            i += 1
        else:
            sorted_list.append(right[j])
            j += 1

    sorted_list.extend(left[i:])
    sorted_list.extend(right[j:])
    return sorted_list

In this example, arr is the input list, and each recursive call keeps splitting the data into smaller sub-problems until there’s almost nothing left to split.

You call it like this:

numbers = [34, 7, 23, 32, 5, 62]
sorted_numbers = merge_sort(numbers)
print(sorted_numbers)

Output:

[5, 7, 23, 32, 34, 62]

After the merge step finishes, the result is a sorted array, even though Python is using lists under the hood.

When to Use Merge Sort in Python

Use merge sort when:

• You need a stable sort (it preserves the order of equal elements).
• You’re working with linked lists or large datasets.
• You want consistent performance, even on large or nearly sorted inputs.
• You're learning sorting algorithms and want a solid recursive example.

Compared to other algorithms like bubble sort or insertion sort, merge sort provides better performance, especially with large lists.

Real-World Applications of Merge Sort Python Programs

Sort Numbers in a List

This is a direct and common use of merge sort:

data = [4, 1, 9, 3, 7]
print(merge_sort(data))  # Output: [1, 3, 4, 7, 9]

This works smoothly with integers, and the logic stays the same even if the list grows to thousands of values.

Sort Strings Alphabetically

You can sort strings using the same function:

words = ["banana", "apple", "cherry"]
print(merge_sort(words))  # Output: ['apple', 'banana', 'cherry']

Merge sort compares items using Python's built-in comparison operators.

Custom Sorting with Tuples or Objects

You can adjust the comparison to sort based on a field:

people = [("Alice", 30), ("Bob", 25), ("Charlie", 35)]

def merge_sort_people(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left = merge_sort_people(arr[:mid])
    right = merge_sort_people(arr[mid:])

    return merge_by_age(left, right)

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

sorted_people = merge_sort_people(people)
print(sorted_people)

Learn More About Merge Sort Algorithm Python Style

Merge Sort Time Complexity

• Worst case: O(n log n)
• Average case: O(n log n)
• Best case: O(n log n)

Unlike quicksort, which can degrade to O(n²) in the worst case, merge sort always stays consistent.

Merge Sort Space Complexity

Merge sort needs additional memory for temporary arrays during merging. Its space complexity is O(n). That’s the tradeoff for guaranteed performance and stability.

Merge Sort vs Built-in sorted()

Python’s built-in sorted() function uses a hybrid sorting algorithm called Timsort, which combines merge sort and insertion sort. It’s optimized for real-world use, but if you’re studying algorithms or customizing sort behavior, writing your own merge sort implementation in Python helps you learn more deeply.

Merge Sort Implementation Python Tip: Use Slicing Wisely

List slicing like arr[:mid] creates new lists and adds overhead. If you're optimizing for performance, avoid slicing by passing indices:

def merge_sort(arr, start, end):
    # In-place version if you're optimizing

But for readability and simplicity, the slicing version works well for most purposes.

Another way to think about those slices is that you’re repeatedly splitting the list into smaller sublists until each one is easy to combine.

Advanced Use Cases

Sorting Linked Lists

Merge sort is ideal for sorting linked lists since it doesn’t require random access. In contrast, algorithms like quicksort rely on indexing, which is inefficient in linked structures.

External Sorting

For massive datasets that can’t fit into memory, you can use merge sort as part of external sorting. Break the data into chunks, sort each chunk, and then merge them.

Sorting Objects with Custom Keys

Use key functions to sort by custom logic:

items = [{"price": 10}, {"price": 5}, {"price": 20}]

def key_func(item):
    return item["price"]

sorted_items = sorted(items, key=key_func)

If you're writing your own merge sort Python program and need custom keys, you can modify the merge logic to use the key function for comparison.

What Happens During the Merge Step

The merge step is where the magic happens. You compare two halves item by item in each iteration, append the smaller one, and move forward.

Once one side runs out, you simply append the remaining elements from the other side. That’s why the last two lines of the merge() function use extend().

If you picture the two halves as tiny chunks pulled from bigger subarrays, merging is basically the process of turning those smaller pieces into one clean, sorted result.

Merge Sort vs Selection Sort

If you’re learning sorting algorithms, it helps to compare merge sort to selection sort.

Selection sort repeatedly scans the list to find the smallest value and moves it into place. It’s easier to understand at first, but it tends to be much slower for large lists. Merge sort, on the other hand, splits the data and combines it back efficiently, so it scales far better when your list grows.

Best Practices for Merge Sort in Python

• Use merge_sort() when learning recursion or building a custom sort function.
• Stick to built-in sorted() when you don’t need to control the sort logic.
• Avoid using merge sort with very small lists in production—simpler sorts like insertion sort may be faster.
• If you’re sorting data in-place for memory efficiency, consider using merge_sort() with index-based logic to avoid slicing.

The Python merge sort algorithm gives you a reliable, recursive way to sort any sequence. By breaking the problem into smaller parts and merging results, you get a consistent and stable sort that handles everything from numbers and strings to complex objects.