# 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.