Merge Sort in Python: Step-by-Step Guide + Code

You’ve got data. It needs to be sorted. Sounds like a simple enough problem, but as it turns out, you have several different sorting algorithms to choose from. Bubble sort, quicksort, merge sort, Timsort… if the outcome is the same, how different could these possibly be? The answer is quite different in terms of methodology and, perhaps more importantly, in terms of speed.

This article is for Python programmers who are comfortable with basic Python syntax and want to understand what merge sort is and how it works by dividing and conquering your list of values. You’ll learn how to implement it in Python and when you should use it over Python’s built-in sorted() function. We’ll help you learn the key concepts and get you sorted out once and for all, just keep reading.

What is the Merge Sort Algorithm?

Merge sort, developed by mathematician John von Neumann in 1945, is a divide-and-conquer algorithm for sorting values from smallest to largest. The technique splits an unsorted array into smaller portions, sorts those small pieces, and then strategically merges them back together, ultimately sorting the entire collection of values.

Typically implemented in programming languages with a top-down, recursive approach, merge sort is a stable sorting algorithm with predictable performance. There is no built-in merge sort function in Python, but it’s an important algorithm to understand conceptually, nonetheless, and proves useful for certain situations. You can even customize it to sort tuples or other objects based on specific fields.

How Merge Sort Works

To execute merge sort for a collection of values, you’ll first divide your collection roughly in two halves. Keep dividing until each sub array contains only one element. These smaller arrays are already sorted since they only contain one item each.

Next, start merging your sublists together. Take two neighboring lists, compare the first—and therefore smallest—element from each, and append whichever one is smallest to a separate merged list. Continue doing this until you’ve worked your way through one of the sub arrays. Since you started from sorted segments, you can then just add the remaining items from the other sublist to the end of your merged list.

You’ll repeat this merging strategy on larger and larger sub arrays until you arrive at a final solution: a fully sorted collection. The result is a final sorted list, or sorted array, as it’s often described in discussions of sorting algorithms.

Recursive (Top-Down) Python Merge Sort Implementation

The most common way to write merge sort in Python is through the recursive, top-down approach that we described above. This method starts from the entire list and repeatedly breaks it into smaller lists before merging back together.

A Python implementation of the recursive merge sort algorithm consists of two tasks: divide and merge. While you could create a single Python function for the entire merge sort algorithm, it’s a bit easier to understand as two complementary functions for each job:

• merge_sort() to handle recursive division (calls the merge() function)

• merge() to combine sorted pieces

Divide and Conquer: merge_sort()

The purpose of this key function is to execute the merge sort algorithm by continually dividing the original list of values and calling upon merge() to recombine the sublists.

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

At a high level, this code first checks to see if the list is empty or has a single element. It returns the list if so. If the list has more than one element, however, merge_sort() finds its midpoint and slices the list into two halves, left and right. It does recursive calls to itself, continually slicing the left half as well as the right half until it hits its base case of a list with one or fewer elements.

Once you have smaller sub arrays with only one element, the calls begin returning, and merge(left, right) starts combining the two sorted halves together. The code proceeds by calling merge() as often as it needs to return the full sorted list.

Sort: merge()

The merge() helper function receives two sorted halves and combines them together into a single sorted array.

def merge(left, right):    merged = []    i = 0    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    merged.extend(left[i:])    merged.extend(right[j:])    return merged

merge() starts with an empty result list and two indices that track the current position in each sublist. As long as neither index reaches the end of the sub array, the function compares the current values from the sublists and takes the smaller one. It appends that smaller value to the result list and increments that sublist’s index. Also note that this comparison favors the left value in the case of ties, which contributes to the algorithm’s stability.

Once the code reaches the end of either list segment, it adds the remaining elements from the other segment to the result with the .extend() method before returning the merged list.

Calling merge_sort()

Putting it all together, here’s the final Python code you need to call merge_sort() on an input array. Remember the merge_sort() function calls merge():

numbers = [7, 1, 10, 8, 2, 4, 6, 9]sorted_numbers = merge_sort(numbers)print(sorted_numbers)# Expected result:# [1, 2, 4, 6, 7, 8, 9, 10]

Iterative (Bottom-Up) Approach to Implement Merge Sort Python

Alternatively, you can think of the merge sort algorithm without the recursion in an iterative, bottom-up approach. This take on merge sort treats each individual element as a sorted group of size 1 and merges adjacent groups. In the next step, it merges groups of 2, then 4, and so on. With each pass, the algorithm combines increasingly larger sorted halves until it processes the entire list.

Here’s Python code for the iterative version of merge_sort(). This method still relies on the same merge() helper function to sort the subsections of the list:

def merge_sort_iterative(values):    result = values[:]    width = 1    while width < len(result):        merged = []        for i in range(0, len(result), 2 * width):            left = result[i:i + width]            right = result[i + width:i + 2 * width]            merged.extend(merge(left, right))        result = merged        width *= 2    return result

This method uses loops to avoid recursion, but ultimately, still has the same overall time and auxiliary-space complexity as the top-down approach. Some consider this Python slightly more difficult to read and implement than the recursive version as well.

Merge Sort on Linked Lists

Unlike regular Python lists where you can easily access elements at any index position, each node of a linked list only knows where the next node is. Merge sort works particularly well for linked lists like this because it can process nodes sequentially rather than repeatedly accessing them by index.

Following the top-down approach, you could find the midpoint of a linked list using slow and fast pointers. You’d break the link at the midpoint to get left and right linked lists and then recursively sort each half. Merge the linked lists back together by comparing values at current nodes and linking the smaller node into the merged list. Then, the process continues advancing through the linked sublists like with the standard Python list implementation.

Note that for linked lists, you can merge by relinking existing nodes, and you’ll need very little auxiliary space for the merge operation itself. This is why developers often prefer merge sort for linked lists over other sorting algorithms like quicksort.

Time, Space, and Performance Analysis

You can think about time and space complexity most efficiently not by counting individual operations, but by considering an algorithm’s overall behavior as the size of your collection grows. Practitioners commonly use big O notation to do this. Given a list of length n, O(1) means that the algorithm’s time and space does not depend on the list length; O(n) means the technique grows linearly with the size; O(n2) quadratically; and so on. You can also consider an algorithm’s big-O performance for the best, worst, and average case.

Merge sort is a highly predictable algorithm that operates at O(n log n) time complexity for its best, average, and worst case scenarios. Remember the two main steps of this algorithm: divide and merge. Repeatedly dividing the problem in two halves produces O(log n) levels, while the merging work for each level processes roughly n elements. Overall, merge sort requires O(n log n) time whether the initial elements are already sorted or in a completely random order.

The standard Python implementation presented here requires O(n) auxiliary space to store the various temporary lists created during merging. The recursive call stack also utilizes O(log n) space, but the overall space complexity is O(n) because O(n) dominates O(log n). Removing the recursion with the iterative approach doesn’t affect the space complexity because you still need O(n) space for the temporary sublists. When you work with linked lists, however, you can create a Python implementation with O(log n) auxiliary space for the recursive stack since you can relink nodes during merging, which only needs O(1) space.

Performancewise, merge sort is a stable algorithm with O(n log n) performance. Its main issue is the additional memory required for the temporary intermediate lists. You’re most likely to reach for this algorithm when you need stability, when you want a predictable worst-case scenario, or when you’re working with linked lists.

Merge Sort Versus Other Sorting Algorithms

You’ve thoroughly explored merge sort throughout this article, but it’s worth noting that several other sorting algorithms exist. Let’s discuss a few of them in this section, ending with timsort, the underlying algorithm for Python’s built-in sorted() function.

Bubble Sort

Bubble sort is a simple algorithm and often one of the first taught in computer science courses. It repeatedly compares adjacent values and swaps those in the wrong order, typically needing multiple passes through the list before placing all elements in the correct position. Easy to understand conceptually, you’ll often see bubble sort as a teaching construct rather than a practical sorting technique due to its poor performance on larger lists. In the worst case, bubble sort has O(n2) time complexity, though it only uses O(1) auxiliary space for its usual in-place implementation.

Quicksort

Quicksort is a divide-and-conquer algorithm like merge sort, but unlike merge sort, which repeatedly divides values into two halves, quicksort chooses one value as a pivot. It then categorizes the remaining elements into partitions that are smaller or larger than the pivot. The partitions then follow the same treatment, recursively, until quicksort sorts all the elements.

This method’s efficiency proves highly dependent upon pivot choice. In the best or average case, quicksort is an O(n log n) algorithm in terms of time, but in the worst case, it can be O(n2). It typically requires less extra memory than merge sort, but quicksort usually isn’t a stable algorithm in that equal elements may end up in a new order.

sorted(): Timsort

Timsort, named after its creator Tim Peters, powers Python’s sorted() function as well as its list.sort() method. It’s a hybrid sorting algorithm that borrows ideas from merge sort as well as insertion sort.

Timsort specifically considers real-world data; for example, it can take advantage of partially sorted values. Unlike traditional merge sort, Timsort looks for existing sorted runs, sequences that are already in the right order, rather than recursively creating two sorted halves. It lengthens shorter runs using insertion sort and then combines runs together in a merge-sort style until it has sorted the entire collection.

In the worst case, Timsort runs in O(n log n) time just like merge sort; however, it can be O(n) for best-case scenarios. It’s a stable algorithm that Python developers have implemented in both sorted() and the .sort() method.

You can use sorted() on any iterable, including lists, while .sort() is a list method. Both methods support optional key and reverse arguments. The main difference between these two is that the .sort() method sorts a list in place while sorted() operates on a list and returns a sorted version of that list.

You will typically just use sorted() or .sort() when you want to sort a list of values in Python rather than implementing merge sort or some other sorting algorithm from scratch. You may still choose to write your own sorting technique when handling linked lists, considering particular algorithmic requirements, or other specialty cases.

Real-World Applications of Merge Sort

While you’ll generally rely on sorted() or list.sort() to create sorted lists, you may find implementing merge sort useful when working with linked lists such as tracking browser history, music playlists, or ordered sequences that change frequently. You could also turn to merge sort when sorting large amounts of input data that are too big to fit into memory. With large datasets, you can sort individual chunks of data before merging the sorted chunks later. You might also find merge sort useful for sorting portions of data in parallel with distributed computing.

Wrapping Up

Merge sort gives you a stable, predictable way to sort your values. While there isn’t a built-in version of merge sort in Python, you can relatively easily implement your own with a top-down (recursive) or a bottom-up (iterative) approach. Merge sort predictably has O(n log n) time complexity for the best, average, and worst cases, but it does typically require O(n) auxiliary space, which is more than some other sorting algorithms require. Instead of writing merge sort from scratch, you’ll likely turn to Python’s sorted() function or its list.sort() method most of the time, both of which use Timsort under the hood.

Just like other algorithms to create sorted arrays, merge sort comes with its own pluses and minuses. Try out the AI Tutor starting from the prompt below to compare merge sort with other options: