Merge Sort using Python Programming

As the output, we are required to get the sorted array.

Look at the given example to understand the working with input and output.

Input:

array: {3 5 1 2 6}

Output:

array: {1 2 3 5 6}

Input:

array: {56 9 11 7 60}

Output:

array: {7 9 11 56 60}

Algorithm

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.

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

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.

Python program for Merge Sort

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)

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

Conclusion

We have concluded the significance of merge sort in this tutorial. Also, the implementation part has been shown to produce the program's desired output.