Sorting Algorithms in Python — Merge Sort

Here is the second post about sorting algorithms. The one that I’m going to show you today is surely nicer than the first one: Merge Sort.

This sorting algorithm has a very popular creator: our beloved von Neumann. Let’s dive into it.

How Merge Sort works

Merge Sort uses a divide and conquer approach (divide-et-impera for the Latin lovers); the starting array (of dimension n) is divided into two sub-arrays of dimension n/2.

This process is looped until reaching a single-value array; those arrays are then reordered. Okay, it’s pretty messy. Let’s see if this GIF can help us understand it:

Thanks to Wikipedia

The algorithm is made of two functions:

• Merge: takes two ordered sub-arrays and merges them in a single array
• Merge Sort: divides the array into sub-arrays through recursive calls and then uses the Merge function.

Let’s move on, everything will be clear when we will look at the code.

Algorithm Overview

Since this is the second post about sorting algorithms I will not repeat what are the math notations. If you need to refresh your mind you may look at the first post.

Best-case complexity: O(nlogn)

Worst-case complexity: O(nlogn)

Stable: Yes (if there are two elements with the same value their relative order will be kept)

In-place: Nope (there is not a maximum number of elements saved outside the starting array, in this case, it is proportional to the dimension of the starting array)

Python Implementation

Here is the Python implementation of the Merge function:

This snippet of code shows a few things:

• at line 1 I imported sys because I needed maxsize (as ∞);
• the parameters are the sub-arrays leftarray and rightarray which are considered to be ordered (keep this in mind, it is veeeery important);
• since those two sub-arrays are already ordered we can use two indexes (i and j) to simply check 1-to-1 between the two arrays and reconstruct the right array variable.
• When we will reach the end there will be a check against maxsize (which is the last element of both sub-arrays). Since we loop in range(len(array)) those values will not be added to array.

Here is the Python implementation of the Merge Sort function:

In this case, the code is self-explanatory so I’m not going to fully discuss it. If you have some questions or doubts you may use the comments or contact me on my social pages.

If you want to see the source code you can check my GitHub!

Conclusions

Merge Sort is without any doubt a better sorting algorithm than Insertion Sort. It has also been one of the most popular until recently. The only drawback is that it drains the memory and for this reason, a series of in-place alternatives have been proposed. Merge Sort has been used as the default sorting algorithm in a lot of programming languages (e.g. Java).