Visualization of Merge Sort in Python (Example)

 

In this tutorial, we will visualize how the merge sort algorithm operates.

The table of content is structured as follows:

Let’s dive into it!

 

Creation of Example Data

First, let’s create a sample list in Python that will be used for the following visualizations.

the_list = [-14, 25, 31, 40, -3.5, 856, 1]

As shown, the_list contains seven unordered numbers consisting of negative and positive values.

 

Tree Diagram of Divide Phase

Firstly, [-14, 25, 31, 40, -3.5, 856, 1] is separated into the lists [-14, 25, 31] and [40, -3.5, 856, 1]. Following this, the program flow continues with the left list and divides the list again into two parts [-14] and [25, 31]. Continuing with the left list, no action is made since the sublist [-14] has only one element. Therefore, the execution is returned back to the parent function call. Here, the “parent function call” refers to the previous function call that generated the function call at hand. Follow the steps below.

Divide Phase

When the execution of the left list ends, the execution of the right list, which is [25, 31], begins. As a result, the sublist is divided into 25 and 31. For the merging phase, see the next section.

Tree Diagram of Merge Phase

The merging operation takes place for the first time for [25, 31]. The original order of the list [25, 31] will be returned since the list is already in the correct order. Then the list will be merged with [-14] to form [-14, 25, 31], making the left half of the diagram completely sorted. The procedure will also be done for the right half of the diagram, and the two sublists will be merged in the final step to form the sorted version of the initial list.

Merge Phase

 

Let’s take a deeper look into the final merging step.

Merging Example

Initially, two pointers holding the index of the next element to check are set to the lowest elements of the sublists. At each loop iteration, the pointed elements are compared, the element with a lower value is inserted into the output list, and the pointer with the lower element is set to the next element of the respective sublist.

This procedure is repeated until one sublist has all the elements inserted. Once this point is reached, the remaining elements of the other sublist are inserted into the output list. Just like that, the merging operation is completed!

 

Video, Further Resources & Summary

Do you need more visual explanations on merge sort? Then you should have a look at the following YouTube video of the Statistics Globe YouTube channel.

 

The YouTube video will be added soon.

 

Furthermore, you could have a look at some of the other tutorials on Statistics Globe:

This post has shown how to picture the operations of merge sort. In case you have further questions, you may leave a comment below.

 

Ömer Ekiz Informatics Expert

This page was created in collaboration with Ömer Ekiz. You may have a look at Ömer’s author page to read more about his academic background and the other articles he has written for Statistics Globe.

 

Subscribe to the Statistics Globe Newsletter

Get regular updates on the latest tutorials, offers & news at Statistics Globe.
I hate spam & you may opt out anytime: Privacy Policy.


Leave a Reply

Your email address will not be published. Required fields are marked *

Fill out this field
Fill out this field
Please enter a valid email address.

Top