Visualizaton of Merge sort using Matplotlib

Visualizing Merge Sort with Python and Matplotlib

Sorting algorithms are fundamental to computer science, and understanding their inner workings can be challenging. Visualizing these algorithms can make the learning process more intuitive. In this article, we'll explore how to animate the Merge Sort algorithm using Python's Matplotlib library, providing a clear and engaging way to grasp its mechanics.

What Is Merge Sort?

Merge Sort is a divide-and-conquer algorithm that divides an array into two halves, recursively sorts them, and then merges the sorted halves. This approach ensures that the algorithm runs in O(n log n) time, making it efficient for large datasets. Unlike algorithms like Quick Sort, Merge Sort is stable, meaning it preserves the relative order of records with equal keys.

Setting Up the Environment

Before we begin, ensure you have Python installed along with the necessary libraries. You'll need:

pip install numpy matplotlib

These libraries will help us generate the data and create the animations.

Implementing Merge Sort with Visualization

We'll create a function to perform Merge Sort and record the state of the list after each merge operation. This allows us to visualize the sorting process step by step.

import numpy as np
import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation
import random

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]

        yield from merge_sort(left_half)
        yield from merge_sort(right_half)

        i = j = k = 0
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1
            yield arr

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

        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1
            yield arr

def visualize_merge_sort():
    arr = [random.randint(1, 100) for _ in range(50)]
    fig, ax = plt.subplots()
    bars = ax.bar(range(len(arr)), arr, align="edge")

    def update_bars(arr, bars):
        for bar, height in zip(bars, arr):
            bar.set_height(height)

    ani = FuncAnimation(fig, update_bars, frames=merge_sort(arr), fargs=(bars,), repeat=False, interval=100)
    plt.show()

visualize_merge_sort()

This code creates a bar chart that updates with each frame, showing the progression of the Merge Sort algorithm.

Enhancing the Visualization

To make the visualization more informative, you can add labels to indicate the number of operations performed and highlight the elements being compared or merged. This provides a clearer understanding of the algorithm's behavior at each step.

Conclusion

Visualizing algorithms like Merge Sort can significantly enhance your understanding of their operations. By animating the sorting process, you can observe how the algorithm progresses and how elements are moved, making the learning experience more engaging and effective.