Python Program for Iterative Merge Sort

Merge sort is an efficient sorting algorithm that follows the "Divide and Conquer" method to sort an array. In this tutorial, we will sort an array with help of an iterative merge sort algorithm.

Iterative Merge Sort - A basic Introduction

Merge Sort operation can also be done by an iterative method. We can also implement merge sort iteratively in a bottom-up manner.

1. We start by sorting all subarrays of 1 element; then merge the result into a subarray of 2 elements
2. Then merge results into a subarray of 4 elements.
3. The same procedure will be followed until the array is sorted.
4. The unmerged sublist element count will be isolated until the final merge call can be found out using the remainder.
5. Now, the array is sorted

The below diagram will help you for understanding better:

Algorithm

As of now, we have a rough understanding of the Merge Sort operation. Let's have a look at the Algorithm followed by code for a better understanding:

1. Define a function merge()
2. Pass 5 parameters temp, from, to, mid, S
3. Merge two sorted sublists with help of this function
4. Copy remaining elements
5. Copy this to reflect the original list in sorted order
6. Create a function Merge_Sort()
7. Iteratively sort sublist using the temporary list
8. Divide the list into blocks
9. The list is sorted now
10. Print the resulting list

Program for Iterative Merge Sort

As discussed above in the algorithm, let us now dive into the programming part of the Iterative Merge Sort operation influenced by the algorithm.

def merge(S, temp, From, mid, to):
 
    a = From
    b = From
    c = mid + 1
 
    while b <= mid and c <= to:
        if S[b] < S[c]:
            temp[a] = S[b]
            b = b + 1
        else:
            temp[a] = S[c]
            c = c + 1
        a = a + 1
 
    # remaining elements
    while b < len(S) and b <= mid:
        temp[a] = S[b]
        a = a + 1
        b = b + 1
 
    # copy back 
    for b in range(From, to + 1):
        S[b] = temp[b]
 
 
# Iterative sort
def Merge_Sort(S):
 
    low = 0
    high = len(S) - 1
 
    # sort list
    temp = S.copy()
 
    d = 1
    while d <= high - low:
 
        for b in range(low, high, 2*d):
            From = b
            mid = b + d - 1
            to = min(b + 2*d - 1, high)
            merge(S, temp, From, mid, to)
 
        d = 2*d
 
# Iterative implementation
if __name__ == '__main__':
 
    #driver code
    S = [4, 2, 3, 1, 6, 5]
    print("The Original array is: ", S)
    Merge_Sort(S)
    print("Array after sorting is: ", S)

The Original array is: [4, 2, 3, 1, 6, 5]
Array after sorting is: [1, 2, 3, 4, 5, 6]

Conclusion

In this tutorial, we have performed an Iterative merge sort operation in python to sort an array. The worst-case time complexity is O(n*log(n) and the space complexity is O(n).