Learn about Merge Sort in Python

Introduction

Sorting means rearranging the data items of an array or list in a specific order. The sequence can be Ascending or Descending order.

Merge sort is one of the prevalent sorting algorithms which follows the divide and conquer algorithm like Quicksort. If you are learning data structure, then you must learn about the Merge Sort algorithm.

Let's get to the main point. One question that every student has first is How does merge sort work, right?

OK, let's talk about it.

How does merge sort works?

• The given array divides into two halves.

• The sub-arrays again divide into two halves until the length of the array becomes one.

• Now the merge(arr, left, right) function takes the left and right sub-array, and the parent array from bottom to top to merge two halves into one in a sorted manner.

This picture will help you to grab the logic of merge sort more deeply.

Code

'''Program Merge Sort in Python'''
def merge(arr, leftArray, rightArray):
    len1 = len(leftArray)
    len2 = len(rightArray)
    i = j = k = 0

    while (i < len1 and j < len2):
        if leftArray[i] <= rightArray[j]:
            arr[k] = leftArray[i]
            i += 1

        else:
            arr[k] = rightArray[j]
            j += 1
        k += 1
    
    while (i < len1):
        arr[k] = leftArray[i]
        k += 1
        i += 1
    while (j < len2):
        arr[k] = rightArray[j]
        k += 1
        j += 1

def mergeSort(arr):
    size = len(arr)
    if size < 2:
        return
    
    # mid is now float type
    mid = size/2
    
    # converting mid to integer
    mid = int(mid)
   
    leftArray = [0] * mid
    rightArray = [0] * (size - mid)
    

    for i in range(0, mid):
       
        leftArray[i] = arr[i]
    for j in range(mid, size):
        
        rightArray[j - mid] = arr[j]

    mergeSort(leftArray)
    mergeSort(rightArray)
    merge(arr, leftArray, rightArray)

def printArray(arr, n):
    for i in range(0, n):
        print(arr[i], end=' ')
    print("\n")


if __name__ == "__main__":
    arr = [5, 2, 1, 4, 3, 6, 8, 7]
    size = len(arr)

    print("Before Sorting: ")
    printArray(arr, size)

    mergeSort(arr)

    print("After Sorting: ")
    printArray(arr, size)

Output

Before Sorting:
5 2 1 4 3 6 8 7

After Sorting:
1 2 3 4 5 6 7 8

Complexity Analysis

Complexity analysis is one of the most important components of any algorithm. It describes the efficiency of an algorithm in terms of time complexity and space complexity.

The Time complexity of merge sort

Recall the merge sort algorithm requires logn passes. Each pass of the algorithm merges the n element. So at most n comparisons will require for each pass.

As a conclusion for both the worst and best cases, the time complexity is O(nlogn).

The Space complexity of merge sort

Extra Space/Space complexity: O(n)