Program for Merge Sort using Python

Introduction

The task is to sort the given array elements using merge sort. Merge sort is yet another sorting algorithm based on divide and conquer mechanism.

Program

def merge_arr(arr, x, mid, y):
    temp1 = mid - x + 1
    temp2 = y - mid
    left = [0] * (temp1)
    right = [0] * (temp2)
    for i in range(0, temp1):
        left[i] = arr[x + i]
    for j in range(0, temp2):
        right[j] = arr[mid + 1 + j]
    i = 0
    j = 0
    l = x
    while i < temp1 and j < temp2:
        if left[i] <= right[j]:
            arr[i] = left[i]
            i += 1
        else:
            arr[l] = right[j]
            j += 1
        l += 1
    while i < temp1:
        arr[l] = left[i]
        i += 1
        l += 1
    while j < temp2:
        arr[l] = right[j]
        j += 1
        l += 1
def sort(arr, x, y):
    if x < y:
        mid = (x+(y-1))//2
# Sorting two halves
        sort(arr, x, mid)
        sort(arr, mid+1, y)
        merge_arr(arr, x, mid, y)
       
ip_arr = [89, 2, 15, 3]
sort(ip_arr, 0, len(ip_arr) - 1)
print("The sorted array is :")
for i in range(len(ip_arr)):
    print(ip_arr[i])

Output

Program for Merge Sort using Python

Explanation

There are two methods: merge_arr() and sort(). The sort() method sorts the two halves of the given array (arr[i…m] and arr[m+1…j) and merge_arr() merges the two halves assuming they are sorted.

Leave a comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.