Originally published on CodingCush .
Merge sort is a sorting algorithm that splits a list in half again and again until every piece has one value, then merges those tiny sorted pieces back together in order. It takes about the same amount of work no matter how shuffled the input is, which is why it is a favourite in interviews and in real code, including Python's own sorted() . In this guide you will dry run it by hand, write the complete Python version, and test its speed against sorted(). All outputs are from real runs on Python 3.12.3.
How Merge Sort Works, in Plain Words
Imagine sorting a messy pile of numbered cards with a friend helping. You split the pile in half, your friend splits their half in half, and so on, until everyone holds a single card. Then you pair up and merge your sorted piles: each pair compares the top card of each pile, takes the smaller one, and repeats until one neat pile is left.
That is the whole idea, and it has a proper name: divide and conquer.…