Merge Sort Algorithm: Visualization and Animation

Merge Sort is one of the most efficient and widely used sorting algorithms. It follows the divide-and-conquer approach, which means it breaks down a problem into smaller subproblems, solves them separately, and then combines the results. In this article we will go through visualization and animation of various steps involved in merge sort algorithm.

Brief recap of how Merge Sort Algorithm Works

Merge sort algorithm contains 3 core steps:

  1. Divide: Split the array into two halves.
  2. Conquer: Recursively sort each half.
  3. Combine: Merge the sorted halves back together.

Refer to these articles for better understanding on how merge sort algorithm works:

Visualization of Various Steps

Let’s assume that the merge sort algorithm is given as input the below list:

The algorithm first divides the input list into two equal halves.

We divide each of the lists again into two halves.

We divide each of the lists again into two halves.

We now have eight sub lists and this time, the size of each of the sublist is 1. So we can say that all the sublists are already in order. So now we can consider two sublists in groups and merge them together into a single sorted list. There are 8 sublists and after merging 2 sublists in groups, we create 4 sublists of length two and all the four sublists are individually sorted.

We now have four sorted sub lists and we can merge 2 lists in groups and form 2 sorted sublists from 4 sorted sublists using the merge routine.

We now have just two sorted sublists and so we can merge both the sublists into a single list, which is the final sorted list we require.

Try out the step by step slideshow provided below for better understanding of the algorithm at a granular level.

Step By Step Slide Show

Below is the step by step visualization of merge sort algorithm implemented via recursion:

Click on the next and previous buttons to move forward or backward in the slideshow.