Merge Sort Program in Python

In this tutorial, you will learn how merge sort work and how to perform merge sort with example.

The Merge sort works by splitting the input list into two halves, repeating the process on those halves, and finally merging the two sorted halves together.

Example :

    
# python program to sort array or list using merge sort
def mergeSort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left = arr[:mid]
        right = arr[mid:]

        mergeSort(left)
        mergeSort(right)

        i = 0
        j = 0
        
        k = 0
        
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
              arr[k] = left[i]
              i += 1
            else:
                arr[k] = right[j]
                j += 1
            k += 1

        while i < len(left):
            arr[k] = left[i]
            i += 1
            k += 1

        while j < len(right):
            arr[k]=right[j]
            j += 1
            k += 1
    return arr

arr = [45,22,65,78,9,23,89,52]

print("Before Sorted :: ",arr)
print("After Sorted :: ",mergeSort(arr))
       

Output :

    
Before Sorted ::  [45, 22, 65, 78, 9, 23, 89, 52]
After Sorted ::  [9, 22, 23, 45, 52, 65, 78, 89]
    

The algorithm works in O(n.logn). This is because the list is being split in log(n) calls and the merging process takes linear time in each call.