Program to implement merge sort in Python

In the python programming article, we are going to learn

• program to implement merge sort in python

---

Program to implement merge sort in Python

The program to implement merge sort is as follows:

 

# Owner : TutorialsInhand Author : Devjeet Roy

def merge(arr, l, m, r): 
    n1 = m - l + 1
    n2 = r - m 
    Left = [0] * (n1) 
    Right = [0] * (n2)   
    for i in range(0 , n1): 
        Left[i] = arr[l + i]   
    for j in range(0 , n2): 
        Right[j] = arr[m + 1 + j] 
    i = j = 0
    k = l      
    while i < n1 and j < n2 : 
        if Left[i] <= Right[j]: 
            arr[k] = Left[i] 
            i += 1
        else: 
            arr[k] = Right[j] 
            j += 1
        k += 1
    while i < n1: 
        arr[k] = Left[i] 
        i += 1
        k += 1
    while j < n2: 
        arr[k] = Right[j] 
        j += 1
        k += 1

def merge_sort(arr,l,r):
    if l < r:  
        m = (l+(r-1))//2 
        merge_sort(arr, l, m) 
        merge_sort(arr, m+1, r) 
        merge(arr, l, m, r) 
    
    return arr


if __name__ == "__main__":
    marks = [22,66,43,58,98,42,77,56,66]
    result = merge_sort(marks,0,len(marks)-1)

    print("The sorted marks: ", result)

The output of the program is as follows:

 

PS C:\Users\DEVJEET\Desktop\tutorialsInHand> python code.py
The sorted marks:  [22, 42, 43, 56, 58, 66, 66, 77, 98]

Few important tips about the proram

1. Merge sort follows divide and conquer paradigm of problem solving.

2. It splits the input list into two halves, repeating the process on those halves and then finally merging the two sorted halves.

3. The time complxity of the the algorithm is O(nlogn).