Iterative Bottom Up Merge Sort in Python (Example)
In this tutorial, you’ll learn how to implement the iterative merge sort algorithm in Python.
The article consists of these contents:
Let’s dive into it:
Creation of Exemplifying Data
Let’s first create some exemplifying data in Python:
my_list = [-1, -5, -40, 100, 589, 27, -95] # initializing example integer list
Now that we have a sample list, let’s go into the algorithm!
Example: Implementing Iterative Bottom Up Merge Sort
When merge sort is mentioned, usually the recursive merge sort comes to mind, in this tutorial we will explore how to implement it in an iterative way. The procedure of iterative merge sort is just like the recursive merge sort, which can be described in 3 steps:
Step 1: Split the list into sub-lists of size 1.
Step 2: Merge adjacent sub-lists to create new sorted sub-lists.
Step 3: Repeat step 2 until only one sorted sub-list remains.
def bottom_up_merge_sort(my_list): # defining bottom_up_merge_sort function n = len(my_list) width = 1 # initializing width while width < n: for i in range(0, n, width * 2): left = i mid = min(i + width, n) right = min(i + width * 2, n) merge(my_list, left, mid, right) # calling the merge function width *= 2 return my_list
The width variable indicates the sizes of the sublists being merged at each iteration of the for loop. In the beginning, we set the width=1.
Then inside the for loop, at each iteration; we set left, mid, and right, and call the merge function with these variables. The variables are indicators of the current sublists that are being merged, left indicates the starting point of the left sublist, mid points to the end of left sublist/beginning of right sublist and right is the index for the end of the right sublist.
Once the for loop terminates, in other words, the loop merges all of the sublists with size a. At each iteration, the widths are doubled to the 2a length. This process is continued until the entire list is merged and sorted.
Let’s now check the content of the merge() function used in previously defined bottom_up_merge_sort()!
def merge(my_list, left, mid, right): # defining merge function temp = [] # initializing empty temp list i = left j = mid while i < mid and j < right: if my_list[i] < my_list[j]: # checking if the left sublist has the lower element temp.append(my_list[i]) i += 1 else: temp.append(my_list[j]) j += 1 while i < mid: # filling the list with remainders of the left sublist temp.append(my_list[i]) i += 1 while j < right: # filling the list with remainders of the right sublist temp.append(my_list[j]) j += 1 for k in range(left, right): # setting the values of the temp list to the main list my_list[k] = temp[k - left]
Initially, the function generates an empty list named temp, then compares the lowest elements from both of the sublists and inserts them to the list temp in increasing order. The execution ends when all of the elements of temp have been assigned to their places in the main list. So we can say that the merge() function merges two sublists in a sorted manner
bottom_up_merge_sort(my_list) # calling the function print(my_list) # printing sorted result # [-95, -40, -5, -1, 27, 100, 589]
Finally, once we call the bottom_up_merge_sort() function, we can see that it takes an unsorted list as input and sorts the list without using a recursive approach. Here is the full code for your convenience:
my_list = [-1, -5, -40, 100, 589, 27, -95] # initializing example integer list def bottom_up_merge_sort(my_list): # defining bottom_up_merge_sort function n = len(my_list) width = 1 # initializing width while width < n: for i in range(0, n, width * 2): left = i mid = min(i + width, n) right = min(i + width * 2, n) merge(my_list, left, mid, right) # calling the merge function width *= 2 return my_list def merge(my_list, left, mid, right): # defining merge function temp = [] # initializing empty temp list i = left j = mid while i < mid and j < right: if my_list[i] < my_list[j]: # checking if the left sublist has the lower element temp.append(my_list[i]) i += 1 else: temp.append(my_list[j]) j += 1 while i < mid: # filling the list with remainders of the left sublist temp.append(my_list[i]) i += 1 while j < right: # filling the list with remainders of the right sublist temp.append(my_list[j]) j += 1 for k in range(left, right): # setting the values of the temp list to the main list my_list[k] = temp[k - left] bottom_up_merge_sort(my_list) # calling the function print(my_list) # printing sorted result # [-95, -40, -5, -1, 27, 100, 589]
I hope this tutorial was helpful in understanding how to implement Iterative Bottom Up Merge Sort in Python! If you have any unclear points, feel free to ask. Until the next tutorial!
Video, Further Resources & Summary
Some time ago, I have published a video on my YouTube channel, which illustrates the Python programming codes of this article. Please find the video instruction below:
The YouTube video will be added soon.
In addition, you could read the related tutorials on this website. I have released numerous related articles already:
- Merge Sort Dictionary in Python
- Merge Sort Counting Inversions in Python
- Recursive Merge Sort in Python
- Function & Library for Merge Sort in Python
- k-way Merge Sort in Python
- All Python Programming Tutorials
To sum it all up, in this Python programming tutorial, you have learned how to sort a list with iterative merge sort. If you have any further questions, please let me know in the comments below. Furthermore, please subscribe to my email newsletter to receive updates on new articles.
This page was created in collaboration with Ömer Ekiz. Have a look at Ömer’s author page to get further information about his professional background, a list of all his tutorials, as well as an overview of his other tasks on Statistics Globe.
I’m Joachim Schork. On this website, I provide statistics tutorials as well as code in Python and R programming.
