Python Program for Merge Sort

Last Updated on March 14, 2023 by Prepbytes

In this article, we are going to understand Merge Sort. Merge sort is a very popular sorting algorithm based on the principle of the Divide and Conquer Algorithm.

Before understanding the Merge sort let’s start with Divide and Conquer Algorithm. In this Divide and Conquer Algorithm a problem is divided into multiple sub-problems then each sub-problem is solved individually and combined to form the final solution.

The above image is showing how Merge sort works on the principle of Divide and Conquer Algorithm.

Merge Sort Algorithm

In Merge sort algorithm we repeatedly divides the array into two halves until we reach array of length one.

This algorithm consists of two functions:

• MergeSort function: MergeSort Function divides the whole array into two halves until we reach the array of length one.
• Merge function: Merge function merges the sorted sub arrays until we get the original array.

Basic Pseudo Code for Merge Sort:

MergeSort(A, p, r): 
    if p > r 
        return
    q = (p+r)/2
    mergeSort(A, p, q)
    mergeSort(A, q+1, r)
    merge(A, p, q, r)

To sort the whole array, you must call MergeSort(A, 0, length(A)-1).

As shown in the above figure the merge sort algorithm recursively divides an array in half until it reaches the base case of a one-element array. The merge function then merges the sorted sub-arrays to incrementally sort the entire array.

Merge Sort Function:

The merge sort algorithm divides the given array into two equal halves and sorts them recursively. This function has base case. The base case written stops the further recursive calls. As we already know that in the merge sort algorithm the array is repeatedly divided into two halves until the length of array reaches 1.

The another part of this function finds the middle value (mid) which is used to divide the array into two halves. The first half is from start_index to mid and the second half is from mid+1 to end_index.

Merge Sort()

    mid= (left+right)/2
    mergesort(array, left, mid)
    mergesort(array, mid+1, right)
    merge(array, left, mid, right)

The line number 1 is for finding the middle element of the array. After finding the middle element we are recursively calling MergeSort function on both halves. When the control reaches back to the line number 4 the both subarray will be already sorted and now our task will be to merge them to find the sorted original array.

Merge Function:
The merge function works as follows:

1. In First step, we create copies of arrays. The first array contains the elements from [start_index,middle] and the second from [middle+1,end_index].
2. In Second step, we traverse both copies of the array with the help of pointers to compare the pointed values and select the smaller value of these two values and add them to the sorted array.
3. In the Last step When the array runs out of elements, it picks up the remaining elements and puts them into a sorted array.

Code

# Python program for implementation of MergeSort

# Merges two subarrays of arr[].
# First subarray is arr[l..m]
# Second subarray is arr[m+1..r]


def merge(arr, l, m, r):
    n1 = m - l + 1
    n2 = r - m

    # create temp arrays
    L = [0] * (n1)
    R = [0] * (n2)

    # Copy data to temp arrays L[] and R[]
    for i in range(0, n1):
        L[i] = arr[l + i]

    for j in range(0, n2):
        R[j] = arr[m + 1 + j]

    # Merge the temp arrays back into arr[l..r]
    i = 0	 # Initial index of first subarray
    j = 0	 # Initial index of second subarray
    k = l	 # Initial index of merged subarray

    while i < n1 and j < n2:
        if L[i] <= R[j]:
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1
        k += 1

    # Copy the remaining elements of L[], if there
    # are any
    while i < n1:
        arr[k] = L[i]
        i += 1
        k += 1

    # Copy the remaining elements of R[], if there
    # are any
    while j < n2:
        arr[k] = R[j]
        j += 1
        k += 1

# l is for left index and r is right index of the
# sub-array of arr to be sorted


def mergeSort(arr, l, r):
    if l < r:

        # Same as (l+r)//2, but avoids overflow for
        # large l and h
        m = l+(r-l)//2

        # Sort first and second halves
        mergeSort(arr, l, m)
        mergeSort(arr, m+1, r)
        merge(arr, l, m, r)


# Driver code to test above
arr = [12, 11, 13, 5, 6, 7]
n = len(arr)
print("Given array is")
for i in range(n):
    print("%d" % arr[i],end=" ")

mergeSort(arr, 0, n-1)
print("\n\nSorted array is")
for i in range(n):
    print("%d" % arr[i],end=" ")

Input:

Given array is
12 11 13 5 6 7 

Output:

Sorted array is
5 6 7 11 12 13

Dry Run:

Merge Sort Complexity

Time Complexity:
Best Case Complexity: O(nlog n)
Worst Case Complexity: O(nlog n)
Average Case Complexity: O(n*log n)

Space Complexity:
The space complexity of merge sort is O(n).

Merge Sort Applications:-

• Inversion count problem
• External sorting
• E-commerce applications

Conclusion:
Merge sort is a famous and very efficient sorting algorithm that utilises the divide and conquer technique of sorting.
The disadvantage of merge sort is that it uses extra memory space to store the temporary copies of arrays before merging them.

FAQs

1. Is Merge sort In Place?
No, In merge sort the merging step requires extra space to store the elements that’s why it is not in place sorting algorithm.

2. Is Merge sort Stable?
Yes, merge sort is stable.

3. Is Merge sort fastest sorting algorithm?
No, The Merge sort is very efficient algorithm but not the fastest one.