Merge Sort Example | Step by Step with Figures

Merge sort is a divide and conquer type algorithm. It follows the basic process of divide and conquers. For the example of merge sort, Assume that an array 'A' with 12 items as following given below the figure,

Fig. 01: The data array with 12 items

The merge sort algorithm stated the two main themes,

1. We have to divide an unsorted list into as many sublists as possible until the list of the array has been sorted properly.

2. We have to repeatedly merge the sublists until we find a sorted list.

Example of Merge Sort with figures

Now, we are going to apply the two main bases of this algorithm with the proper figure to understand the example correctly.

Each pass of the merge sort algorithm will start at the opening of the array 'A' and the generate pairs should have merged of sorted subarrays or sublists as shown in the following steps.

Step 1: Find the midpoint of the array list and make pair from the beginning of the array list. There will be six pairs and those are called sublists of the list.

Fig. 02: Pairs or sublist of the array 'A'

Fig. 03: Separating to pairs

Step 2: Each divided pair need to be sorted. The numbers 40 and 30 interchange their position. The 90 and 25 repositioned and also 60 and 88 numbers. The others are already sorted. So, there won't need any operations.

Fig. 04: Interchanging of numbers

Step 3: Now sorting is done in the sublists of the array. As the algorithm stated that we have to again remerge the numbers and sort them again and again. Pairs are now: {30, 40, 11, 59}, {70, 95, 45, 69}, and {25, 99, 60, 88}.

Fig. 05: Merging of sorted pairs

Step 4: According to the algorithm, we have to sort the pairs i.e. newly generated sublists as the following figure. 30, 40, and 11 need to interchange their position because they are not in a sorted way. Also, the middle and last sublist need to be sorted. 70, 95, 45, and 69 need to be repositioned. Also, 99, 60, and 88 need to interchange their location in the list.

Fig. 06: Interchanging of locations

Step 5: After the sorting of the three sublists, we have to merge them again. The beginning of the two pairs will be merged and sorted according to the above process. In this step, the 59 and 45 will interchange their location for the sorting process.

Fig. 07: Merging of the sublists

Step 6: We are in the last step, there are now only newly generated two pairs or sublists. The last two pairs will merge and the sorting of this array list will be processed. In the last step, the numbers 30, 40, 45, 59, 69, 95, 25, 60, and 88 will be rearranged according to interchanging their location in the list.