Python Program for Merge Sort

Last Updated on November 30, 2023 by Ankit Kochar

Merge Sort is a widely-used sorting algorithm known for its efficiency and stability. It operates on the principle of dividing an array into two halves, sorting each half separately, and then merging the sorted halves to produce a fully sorted array. In Python, implementing Merge Sort involves breaking down the sorting process into recursive steps, making use of the "divide and conquer" strategy. This introduction explores the essential concepts behind the Merge Sort algorithm in Python, highlighting its simplicity, effectiveness, and the step-by-step process involved in sorting a list or array.

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.

What is Merge Sort Algorithm in Python?

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:
In conclusion, the Python implementation of the Merge Sort algorithm showcases the elegance and effectiveness of this sorting technique. By recursively dividing and merging, Merge Sort achieves a stable and efficient way of sorting arrays or lists. The clarity and readability of Python code make it an excellent choice for illustrating the intricacies of the Merge Sort algorithm. Understanding and implementing Merge Sort in Python provides developers with a valuable insight into both algorithmic principles and the capabilities of the Python programming language.

FAQs related to Python Program for Merge Sort

Below are some of the FAQs related to Python Program for Merge Sort:

Q1: How does Merge Sort work in Python?
A1: Merge Sort in Python operates by dividing an array into two halves, recursively sorting each half, and then merging the sorted halves to produce a fully sorted array.

Q2: Why is Merge Sort considered efficient?
A2: Merge Sort is considered efficient due to its consistent O(n log n) time complexity, making it suitable for large datasets. Its "divide and conquer" strategy ensures a balanced and predictable performance.

Q3: Can Merge Sort be applied to other data structures besides arrays?
A3: While Merge Sort is commonly used for arrays and lists, its principles can be adapted for other data structures. The key is defining the splitting and merging logic relevant to the specific structure.

Q4: Are there built-in functions for sorting in Python?
A4: Yes, Python provides built-in functions like sorted() and sort() for sorting lists. However, understanding algorithms like Merge Sort enhances the understanding of sorting processes and their underlying principles.

Q5: What are the advantages of using Merge Sort over other sorting algorithms in Python?
A5: Merge Sort offers advantages such as stability, predictable performance, and suitability for large datasets. Its efficiency and simplicity make it a favorable choice in scenarios where a stable, O(n log n) sorting algorithm is required.