C++

Merge Sort C++

You may have heard about the divide and conquer rule when you have worked on C++ programming. The merge sort works on this rule. Using the merge sort, we divide the whole object or array into 2 equal parts and sort both parts independently. If we can’t get the required result, we will repeatedly divide both parts repeatedly. Each divided part will be sorted independently. After the overall sorting, we will merge the divided parts into one. So, we have decided to cover the merge sort technique in this article for those Linux users who are not familiar with it before and looking for something to get help. Make a new file for C++ code.

Example 01:

We have been starting the first example code with the C++ library “iostream.” The C++ namespace is a must before using any input and output object statement in the code. The merge function prototype has been defined. The “divide” function is here to repeatedly divide the whole array into parts. It takes an array, the first index, and the last index of an array in its parameter. Initialized a variable “m” in this function to be used as a mid-point of an array. The “if” statement will check whether the leftmost index is less than the highest point index in an array. If so, it will calculate the mid-point “m” of an array by using the “(l+h)/2” formulae. It will equally divide our array into 2 parts.

We will further divide the already divided 2 segments of an array by recursively calling the function “divide.” To divide the left-divided array further, we will be using the first call. This call takes the array, the left-most first index of an array, as a starting point and the mid-point “m” as the endpoint index for an array in a parameter. The second “divide” function call will be used to divide the second divided segment of the array. This function takes an array, the index of a successor for mid “m” (mid+1) as the starting point, and the last index of an array as the endpoint.

After equally dividing the already divided array into more parts, call the “merge” function by passing it an array, the starting point “l,” the last point ”h,” and the mid-point “m” of an array.

The merge() function will be started with the declaration of some integer variables, i.e., I, j, k, and array “c” of size 50. We have initialized “I” and k with left index “l” and made the “j” a successor of mid, i.e., mid+1. The while loop will continue to process if the value of lowest “I”  is less than and equal to the mid and the value of “j” mid is less than equal to “h” highest point. The “if-else” statement is here.

Within the “if” clause, we will be checking that the first index of array “I” is less than the successor “j” of mid. It will continue to swap the value of the lowest “I” with the lowest “k” of the “c” array. The “k” and “I” will be incremented. The else part will assign the value of index “j” for array “A” to index “k” of array “c.” Both “k” and “j” will be incremented.

There are other “while” loops to check whether the value of “j” is less or equal to mid, and the value of “j” is less or equal to “h.” According to that, values of “k,” “j,” and “I” will be incremented. The “for” loop is here to assign a value “I” for the “c” array to the “I” index of array “ar.” This is all about merging and sorting in one function.

We have declared an integer type array “A” of size 50 and a variable “n” from the main driver function. The user has been asked to enter the total number of values to be saved into the array utilizing the c++ cout object. The “cin” object statement will take the number from a user as input and assign it to the variable “n.” The user will be asked to enter the values in an array “A” via the “cout” clause.

The “for” loop will be initialized, and on each iteration, a value entered by the user will be saved to each index of an array “A” via the “cin” object. After inserting all values into the array, the function call to the “divide” function will be made by passing it an array “A,” the first index “0” of an array, and the last index “n-1”. After the divide function completes its process, the “for” loop will be initialized to display the sorted array using each index of an array. For this, a cout object will be utilized in the loop. In the end, we will be adding a line break using the “\n” character in the cout object.

On compiling and running this file, the user has added 10 elements in an array in random order. The sorted array has been displayed at last.

Example 02:

This example started with the merge() function to merge and sort the divided segments of an original array. It uses the array “A,” left index, midpoint, and the highest index of an array. According to situations, the value in array “A” will be assigned to array “L” and “M.” It will also maintain the current index of the original array and the sub-arrays.

Here comes the sorting part in which we will assign the values of the sub-array to the original array “A” after sorting the sub-arrays. The last two while loops are used to put the left values in the original array after the sub-arrays are already empty.

The sort function is here to sort the original array after getting its left-most and the highest-point index. It will calculate a mid-point from an original array and divide the original array into two parts. These two segments will be sorted by the recursive calling of the “sort” function, i.e., calling a function in itself. After sorting both the segments, the merge() function will be used to merge the two segments into one array.

The “show() function is here to display the merged sorted array on the shell using the “for” loop and cout objects in it.

The main() function is initializing an array “A” and the size “n” for an array. It will show you the unsorted array before using merge sort via the “sort” function call. After that, the “sort” function was called to sort the original array by the divide and conquer rule. At last, the show function has been called again to display the sorted array on the screen.

The code has been appropriately compiled and executed after that. After using the merge sort, the unsorted original array and the sorted array are displayed on our screen.

Conclusion:

This article is used to demonstrate the use of merge sort in C++. The use of the divide and conquer rule in our examples is quite clear and easy to learn. The special recursive call-to-divide function is used to divide the array, and the merge function is used to sort and merge the segmented parts of an array. We hope this article will be the best help for all the users who want to learn merge sort in the C++ programming language.

About the author

Aqsa Yasin

I am a self-motivated information technology professional with a passion for writing. I am a technical writer and love to write for all Linux flavors and Windows.