Python Program For Merge Sort (With Code + Easy Explanation)

In this guide, you will learn about the python program for merge sort.

Sorting is an essential operation in computer science, and merge sort is one of the most efficient and widely used sorting algorithms.

In this article, we will explore how to write a Python program for merge sort and understand its inner workings.

Whether you’re a beginner or an experienced programmer, this comprehensive guide will help you grasp the concepts and master the implementation.

Merge sort is a divide-and-conquer algorithm that recursively divides the input list into smaller sublists, sorts them individually, and then merges them to produce a sorted output.

It is based on the principle of merging two sorted arrays to create a single sorted array.

Merge sort guarantees a stable sorting order, meaning that elements with equal values maintain their relative order after sorting.

How does Merge Sort work?

Merge sort follows a simple yet effective approach to sorting. Here’s a high-level overview of how the algorithm works:

1. Divide: The input list is divided into two equal halves until the base case is reached, i.e., when the sublist contains only one element.
2. Conquer: The sublists are recursively sorted using merge sort.
3. Merge: The sorted sublists are merged together to obtain a single sorted list. This process involves comparing the elements from each sublist and placing them in the correct order.

The merge operation is the key step that differentiates merge sort from other sorting algorithms.

By merging smaller sorted sublists, merge sort gradually builds up the sorted final list.

To implement merge sort in Python, you can use a recursive function that takes an input list and returns the sorted list.

Here’s an example program.

Python Program for Merge Sort

def merge_sort(arr):
    # Base case: if the length of the array is 1 or less, it is already sorted
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    # Divide the array into two halves: left_half and right_half
    left_half = arr[:mid]
    right_half = arr[mid:]
    
    # Recursive calls to merge_sort for sorting the left and right halves
    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)
    
    # Merge the sorted left and right halves
    return merge(left_half, right_half)
    
def merge(left, right):
    result = []  # List to store the merged result
    i = j = 0  # Pointers for iterating through the left and right halves
    
    # Compare elements from the left and right halves and add them to the result list in the correct order
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    
    # Add any remaining elements from the left half to the result list
    while i < len(left):
        result.append(left[i])
        i += 1
    
    # Add any remaining elements from the right half to the result list
    while j < len(right):
        result.append(right[j])
        j += 1
    
    return result


array = [99,2,1,36,13,9]
sorted_array = merge_sort(array)
print("Original Array =", array)
print("Sorted Array   =", sorted_array)

You can run this code on our free Online Python Compiler.

Output

The merge_sort() function recursively divides the input list and merges the sorted sublists using the merge() function.

The merge() function compares the elements from the left and right sublists and constructs the sorted output list.

To understand how the merge sort algorithm works, let’s walk through an example with a given input list [5, 2, 8, 3, 1, 6, 4].

We’ll trace the execution step-by-step.

Python Program for Merge Sort

1. Initial Input: [5, 2, 8, 3, 1, 6, 4]
2. Divide: Split the list into two halves: [5, 2, 8] and [3, 1, 6, 4]
3. Divide: Further divide each sublist: [5] [2, 8] [3, 1] [6, 4]
4. Conquer: Sort the individual sublists: [5] [2, 8] [1, 3] [4, 6]
5. Merge: Merge the sorted sublists: [2, 5, 8] [1, 3, 4, 6]
6. Merge: Merge the final sublists to obtain the sorted output: [1, 2, 3, 4, 5, 6, 8]

By recursively dividing, sorting, and merging the sublists, merge sort guarantees the production of a sorted list.

Merge sort has a time complexity of O(n log n), where ‘n’ represents the number of elements in the list.

This makes merge sort highly efficient for large datasets.

The algorithm’s time complexity remains consistent regardless of the initial order of the elements.

Space Complexity of Merge Sort

The space complexity of merge sort is O(n), where ‘n’ represents the number of elements in the list.

This space complexity arises due to the creation of temporary lists during the merge process.

It is important to consider the available memory when working with large datasets.

Advantages of Python Program For Merge Sort

Merge sort offers several advantages that make it a popular choice for sorting tasks:

1. Efficiency: With a time complexity of O(n log n), merge sort is one of the most efficient sorting algorithms.
2. Stability: Merge sort guarantees a stable sorting order, making it suitable for scenarios where the relative order of equal elements matters.
3. Consistency: The time complexity of merge sort remains the same regardless of the initial order of elements.
4. Suitable for Large Datasets: Merge sort performs well even with large datasets, thanks to its efficient divide-and-conquer strategy.

Disadvantages of Python Program For Merge Sort

While merge sort has numerous advantages, it also has a few limitations:

1. Space Complexity: Merge sort requires additional memory space proportional to the size of the input list, which can be a constraint when working with limited memory.
2. Recursive Nature: The recursive nature of merge sort can lead to stack overflow errors if the depth of recursion exceeds the system’s limitations.
3. Not In-place: Merge sort does not perform in-place sorting, meaning it requires additional memory to store the sorted output.

What is the main advantage of merge sort?

The main advantage of merge sort is its efficiency.

With a time complexity of O(n log n), it performs well even with large datasets, making it suitable for various applications.

Can merge sort handle large datasets efficiently?

Yes, merge sort is known for its efficiency in handling large datasets.

Its time complexity of O(n log n) ensures consistent performance regardless of the size of the input.

Is merge sort a stable sorting algorithm?

Yes, merge sort is a stable sorting algorithm.

It preserves the relative order of elements with equal values during the sorting process.

Does merge sort modify the original list?

The Python program for merge sort provided here does not modify the original list.

Instead, it creates a new sorted list as the output, leaving the original list unchanged.

Is merge sort suitable for sorting linked lists?

Yes, merge sort is well-suited for sorting linked lists.

Its divide-and-conquer strategy can be efficiently implemented on linked list structures.

How does merge sort compare to other sorting algorithms?

Merge sort offers several advantages over other sorting algorithms.

It guarantees stability, performs well with large datasets, and has a consistent time complexity.

However, it requires additional memory due to its non-in-place nature.

In this article, we explored the Python program for merge sort, a powerful sorting algorithm that efficiently sorts a given array or list.

We discussed the step-by-step implementation of merge sort, its time and space complexity, as well as its advantages and disadvantages.

Merge sort’s stability, efficiency, and scalability make it a popular choice in various applications.

So next time you need to sort a list, consider implementing merge sort and enjoy its reliable and efficient performance.

Happy Coding!