Merge Sort Algorithm

Line by Line Explanation of Merge Sort Algorithm in C++

Author has Explained here merge sort briefly with diagram representing and code screenshots and some recommended link also . Also the line by line explanation for the program execution for this algorithm in C++ .

Merge sort is a divide-and-conquer algorithm based on the idea of breaking down a list into several sub-lists until each sublist consists of a single element and merging those sublists in a manner that results into a sorted list.

Diagram Explaining Work of Merge Sort Algo

Now Lets Code For That Algorithm

First Part of the Code (Fig 1)

Line 62 (Fig 1) :- Here starts our program , declaring an array named as myarray of “5” and declaring an integer for carrying the size of array that is “5” named as arr_size . Now asking to the user to enter the elements for the array then printing the array before sorted .

Line 76 (Fig 1) :- Here we are calling the mergeSort function to make them sort , by passing the array and left most index and right most index of the array .

Now Let’s write the code for mergeSort Function

Second Part of the Code (Fig 2)

Line 48 (Fig 2) :- Now in this function we are taking parameters , array , left most index , right most index respectively .

Line 49 (Fig 2) :- In this If , we are checking wether the left most index of array that is 0 is less then the right most index (right most index could be any number , depend of size of array ) . It’s obvious that left most index is always going to zero . So the purpose to check this is to make sure that there is more than one element in array or not .

Line 51 (Fig 2) :- Here we are finding the middle index of the array to divide and conquer .

Before going to next , you should at least heard of Recursive functions , if you don’t then just Google it for a short look.

Line 54 (Fig 2) :- Here we are dividing the array in left part , that why we are passing the parameters as array , left most and middle (which is the right most index for left half of the array) .

Line 55 (Fig 2) :- Here we are dividing the array in right part , thats why we are passing the parameters as array , middle + 1 (which is left most for right half of the array) , right most .

Line 58 (Fig 2) :- Here we are calling the merge function to merge the array by sorting them . And passing the arguments as array ,left most , middle , right most .

NOTE :- In order to understand the recursion that happening in above code , I recommend you to watch the below video from a particular duration that is (11:30 to last).

Now Let’s write the code for merge Function

Third Part of the Code (Fig 3)

Line 4 (Fig 3) :- In this merge function we are passing parameters as array , left most , right most , and middle . And initialising some integers like , i which will be left most index , j which represents the starting of right part of array , and k for left most .

Line 9 (Fig 3) :- Creating a temp array for storing sorted elements .

Line 10 (Fig 3) :- Here we are giving two conditions to run the while loop , first one is to check wether left most index is less than or equal to middle and second thing is to check wether j is less then or equal to right most or not .

Third Part of the Code (Fig 3)

By checking in while loop , we are making restrict to loop to be left part as in left and right one to be in right . Then comparing the elements to swap .

And doing same thing in further while loops , to compare the left part with right part .

Line 34 (Fig 3) :- Storing sorted array in arr to pass in parameter .

Then as in main function , we are printing after calling the merge sort function .

So this was all about Merge Sort , how it works and explanation .