Merge Sort in Python
Introduction
Merge Sort is one of the most famous sorting algorithms. If you’re studying Computer Science, Merge Sort, alongside Quick Sort is likely the first efficient, general-purpose sorting algorithm you have heard of. It is also a classic example of a divide-and-conquer category of algorithms.
Merge Sort
The way Merge Sort works is:
An initial array is divided into two roughly equal parts. If the array has an odd number of elements, one of those “halves” is by one element larger than the other.
The subarrays are divided over and over again into halves until you end up with arrays that have only one element each.
Then you combine the pairs of one-element arrays into two-element arrays, sorting them in the process. Then these sorted pairs are merged into four-element arrays, and so on until you end up with the initial array sorted.
Here’s a visualization of Merge Sort:
As you can see, the fact that the array couldn’t be divided into equal halves isn’t a problem, the 3 just “waits” until the sorting begins.
There are two main ways we can implement the Merge Sort algorithm,