Python Program for Merge Sort

Merge Sort operation follows the divide and conquer method for sorting. In this tutorial, we will perform the Merge Sort operation to sort an array.

Merge Sort - Basic Introduction

A problem is split into multiple sub-problems in merge sort. Each sub-problem is addressed separately. The final result is formed by combining sub-problems. The MergeSort method divides the array in half periodically until we reach a point when we try to MergeSort on a subarray of size 1. The merge function then takes over, merging the sorted arrays into larger arrays until the entire array is merged.

Let us have a rough understanding of merge sort:

1. Consider an array
2. Find the middle point to divide the array into two halves
3. Call merge sort for the first half
4. Call merge sort for the second half
5. Merge both the half
6. The result will be in sorted format

For better understanding let's have a look at the diagram below:

Algorithm

As of now, we have a rough understanding of how merge sort is performed. For better understanding let's dive deep into the algorithm followed by the code:

1. Create a merge_sort() function
2. Initiate array list and divide it into subarrays.
3. Create copies of the subarrays
4. Create three-pointers that maintain indexes.
5. Pick larger elements and place them in the right position
6. Pick the remaining elements and sort them accordingly
7. The result will be sorted array
8. Print the sorted array.

Program for Merge Sort

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

def Merge_Sort(array):
    if len(array) > 1:
        #  mid is the point where the array is divided into two subarrays
        mid = len(array)//2
        Left = array[:mid]
        Right = array[mid:]

        Merge_Sort(Left)
        Merge_Sort(Right)

        i = j = k = 0

        while i < len(Left) and j < len(Right):
            if Left[i] < Right[j]:
                array[k] = Left[i]
                i += 1
            else:
                array[k] = Right[j]
                j += 1
            k += 1

        while i < len(Left):
            array[k] = Left[i]
            i += 1
            k += 1

        while j < len(Right):
            array[k] = Right[j]
            j += 1
            k += 1

# Print the array
def printarray(array):
    for i in range(len(array)):
        print(array[i], end=" ")
    print()

# Driver program
if __name__ == '__main__':
    array = [7, 2, 5, 6, 3, 1, 8, 4]
    print("Orignal Array is: ", array)

    Merge_Sort(array)

    print("Sorted array is: ")
    printarray(array)

Orignal Array is: [7, 2, 5, 6, 3, 1, 8, 4]
Sorted array is:
1 2 3 4 5 6 7 8

Conclusion

In this tutorial, we have performed a Merge Sort operation in python to sort an array. The time complexity of merge sort is O(n*log N ) and the space complexity is O(n). The merge sort can be used in different applications, e-commerce portal is one of the applications.