 Merge sort Visualization with python

#### Never Forget Those Sorting Algorithms By Visualizing them with Python.

###### There are various types of sorting algorithms out there. Sometimes it becomes very difficult to understand their internal working without visualization. Hence I decided to Visualize Sorting Algorithms With Python language with the help of matplotlib.animations library. Bubble Sort on left and Merge Sort on right

NOTE:- In this article, we will also compute the number of operations performed. Hence, will be able to see the time complexity of the sorting algorithm.

As our purpose is to only visualize sorting algorithms with python hence I will be using the merge sort` `for a demonstration but you should implement the rest of them in order to understand the differences among them.

Before we start coding, you must have python 3.3` `or above installed because I have used the `yield from`  feature of generator.

### Let’s Start:-

Firstly you need to import the given libraries. We have used the `random` module in order to generate a random array of numbers to be sorted. The `matplotlib pyplot` and `animation` modules will be used to animate the sorting algorithm.

``import randomimport matplotlib.pyplot as pltimport matplotlib.animation as anim``

Below the given `swap` function will be used to swap the elements in the given array. Defining a separate function is useful as it will be used exhaustively throughout different algorithms.

``def swap(A, i, j):    a = A[j]    A[j] = A[i]    A[i] = a    # also in python A[i],A[j]=A[j],A[i]``

We have used `Merge Sort` to demonstrate this visualization because this is the most popular and one of the best sorting algorithms out there. Merge sort follows `Divide and Conquer` technique for sorting. It divides the array into two subarrays and each of these is sorted by calling the merge sort recursively on them. Our main focus is to visualize the algorithm hence I will not explain the working of it. The following code shows the merge sort and in order to get the intuition on how it works, one can follow this video on youtube jenny’s lecture.

``def merge_sort(arr,lb,ub):    if(ub<=lb):        return    elif(lb<ub):        mid =(lb+ub)//2        yield from merge_sort(arr,lb,mid)        yield from merge_sort(arr,mid+1,ub)        yield from merge(arr,lb,mid,ub)        yield arrdef merge(arr,lb,mid,ub):    new = []    i = lb    j = mid+1    while(i<=mid and j<=ub):        if(arr[i]<arr[j]):            new.append(arr[i])            i+=1        else:            new.append(arr[j])            j+=1    if(i>mid):        while(j<=ub):            new.append(arr[j])            j+=1    else:        while(i<=mid):            new.append(arr[i])            i+=1    for i,val in enumerate(new):        arr[lb+i] = val        yield arr``

Now we will simply create the random list of numbers to be sorted and the length of the array will be decided by the user itself. After that,`if condition` is used to choose the algorithm.

``n = int(input("Enter the number of elements:"))al = int(input("Choose algorithm:  1.Bubble \n 2.Insertion \n 3.Quick \n 4.Selection \n 5.Merge Sort))array = [i + 1 for i in range(n)]random.shuffle(array)if(al==1):    title = "Bubble Sort"    algo = sort_buble(array)elif(al==2):    title = "Insertion Sort"    algo = insertion_sort(array)elif(al==3):    title = "Quick Sort"    algo = quick_Sort(array,0,n-1)elif(al==4):    title="Selection Sort"    algo = selection_sort(array)elif (al == 5):    title = "Merge Sort"    algo=merge_sort(array,0,n-1)``

Now we will create a canvas for the animation using `matplotlib figure `and `axis`. Then we have created the bar plot in which each bar will represent one number of the array. Here `text()` is used to show the number of operations on the canvas. The first two arguments are the position of the `label.transform=ax.transAxes` tells that the first two arguments are the axis fractions, not data coordinates.

``fig, ax = plt.subplots()ax.set_title(title)bar_rec = ax.bar(range(len(array)), array, align='edge')text = ax.text(0.02, 0.95, "", transform=ax.transAxes)``

The `update_plot` function is used to update the figure for each frame of our animation. Actually, this function will pass to `anima.FuncAnimamtion() `that uses it to update the plot. Here we have passed the input array, `rec `which is defined above, and the epochs that keep the track of number of operations performed. One may think that we can simply use integer value instead of a list in epochs but integer like `epoch = 0` cannot be passed by reference but only by value, unlike a list, which is passed by reference. The `set_height()` is used to update the height of each bar.

``epochs = def update_plot(array, rec, epochs):    for rec, val in zip(rec, array):        rec.set_height(val)    epochs+= 1    text.set_text("No.of operations :{}".format(epochs))``

In the end, we create `anima` object in which we pass `frames=algo `that takes generator function(the algorithm is a generator function as it contains yield ) and after that, it passes the generated or updated array to the update_plot` `,fargs` `takes additional arguments i.e. `epochs` and `bar_rec` and `interval` is the delay between each frame in milliseconds.

And finally, we use` plt.show()`` `to plot the animated figure.

``anima = anim.FuncAnimation(fig, func=update_plot, fargs=(bar_rec, epochs), frames=algo, interval=1, repeat=False)plt.show()``

Full code with all sorting algorithms is available in my Github repo. Check it out. And if you like this article, please let me know.

Check out my article on Convert Image to Artistic ASCII Image Using Python

Learn more about the animationFunction

### Pushkara

Woring in the field of I.T. for past 3 years and have expertise in the areas of Machine Learning, App Development(Flutter) and Automation. He loves to write about new technologies and simple projects that can help beginners to start with.

Previous Story

Next Story

## Convert Image to Artistic ASCII Image Using Python

In this article, we will convert any given image to an artistic colored ASCII image using