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

In addition, you could read the related tutorials on this website. I have released numerous related articles already:

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.

Subscribe to the Statistics Globe Newsletter