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.
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.
Let’s take a deeper look into the final merging step.
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:
- k-way Merge Sort in Python
- Merge Sort List in Python
- Function & Library for Merge Sort in Python
- List Comprehension in Python
- Introduction to Python Programming
This post has shown how to picture the operations of merge sort. In case you have further questions, you may leave a comment below.
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.