merge sort

Merge sort is a comparison-based sorting algorithm that arranges a sequence by repeatedly splitting it in half, ordering each half, and merging the sorted halves back into one. Comparison-based means it orders elements by comparing them in pairs, and divide-and-conquer means it breaks a problem into smaller versions of itself, then combines the results. John von Neumann described it in 1945, and it’s also written mergesort.

The recursive top-down version splits the input until each piece holds a single element, which counts as already sorted. It then merges those pieces back in pairs, comparing the front element of each half and copying the smaller one into the output until both halves are consumed. A bottom-up version reaches the same result without recursion, merging runs of size one, then two, then four, and so on.

Step through a full sort below to watch the list divide down to single elements and the sorted runs merge back into one ordered list:

Merge sort runs in O(n log n) time in the best, average, and worst case, so its performance stays predictable regardless of the input’s initial order. That guarantee comes at a cost in space: a standard array implementation needs O(n) auxiliary memory to hold the merged output.

Two properties make it a common building block:

• Stability: Equal elements keep their original relative order, so sorting by one key preserves the order set by an earlier sort.
• Sequential access: The merge step reads each half in order, which suits linked lists and the external sorting of data too large to fit in memory.

Python’s built-in sorted() and list.sort() use Timsort, an adaptive hybrid of merge sort and insertion sort that exploits already-ordered runs.

Related Resources

Tutorial

Thinking Recursively in Python

Learn how to work with recursion in your Python programs by mastering concepts such as recursive functions and recursive data structures.

intermediate python

For additional information on related topics, take a look at the following resources:

• Recursion in Python: An Introduction (Tutorial)
• Sorting Algorithms in Python (Tutorial)
• Introduction to Sorting Algorithms in Python (Course)
• Recursion in Python (Course)
• Thinking Recursively With Python (Course)
• Recursion in Python: An Introduction (Quiz)