Merge sort C++ is one of the very efficient algorithm in programming languages. It is normally used for the sorting of large data. Normally, Quicksort is preferred over Merge Sort because Quicksort has a smaller constant factor. In programming Merge sort is preferred on bubble sort, selection sort and insertion sort.
C++ Merge sort works on a technique of divide and conquer, every time when the merge sorting function calls, it will divide the array into two parts, then the merge function will merged the two divided parts into the sorted array.
Example of Merge Sort Algorithm:-
Merge-Sort (A, p, r) if p < r q= [ (p + r) / 2 ] Merge-Sort (A, p ,q) Merge-Sort (A, q+1 ,r) Merge (A, p, q, r) ………………………………………………….. Merge (A, p, q, r) n1 = q – p + 1 n2 = r – q let Left[1…… n1 + 1] and Right[1…… n2 + 1] be the new arrays For (i equal to 1 and it will run until n1) ……. Left[i]= A[P + i – 1] For (j equal to 1 and it will run until n2) ……. Right[j] = A[q + j] Left [n1 + 1] = infinite value or could store any flag Right [n2 + 1] = infinite value or could store any flag i = 1 j = 1 For (k =p to r) If( Left[i] <= Right[j]) ---- A[k] = Left[i] ---- i = i + 1 Else ---- A[k] = Right[j] ---- j = j + 1
Explanation of Merge Sort in C++:-
Now we will look at the example array of eight elements and will apply merge sorting on it. The example array is A = {2, 3, 14, 10, 8, 1, 12, 9}, now we will discuss its working.
As we can see in an above algorithm, whenever the Merge-Sort function will call, it will check the condition, if p is lesser than r then it will divide the array into two equal parts as shown in an image.
The thing to remember, the functions after the recursion will store into the stack, whenever the condition (p < r) becomes false, then stack will be pop up stored functions and then control will be transferred to these popped up functions.
As we can see the array will continue to divide into parts and then it will started to merge. Remember one thing the sequence of Merge-Sort function and Merge functions could be different in stacks, I haven’t created the stack into this tutorial, so you have to maintain stack by yourself.
As you can see in the above image, first array will be divided into smaller parts then Merge function will continue combining the divided parts into multiple sorted arrays. When all the array parts will combine by the merge function we will get the properly sorted array.
Now I will explain the Merge function, its working and how it has combined the divided individual array elements. I will apply Merge function only the second last part of an procedure, so I could show you example of the working of C++ Merge Sorting. After that you have to apply Merge function on remaining parts of the array by yourself for an exercise.
Working of Merge(A, p, q, r) Function:-
When this function will be called, it takes four arguments, it will create two new arrays named as Left array and right array, it will store half left part of array A into left Array and another half part into Right Array.
Initially the value of i and j is equal to 1 and then the For loop will began.
For( k=p to r)
Here i=1, j=1, k=1, p=1, r=8.
Iteration 1:-
Left[i] <= Right[j] -> condition false.
Therefore A[k] = Right[j] -> A[1] = Right[1].
j will be incremented.
Iteration 2:-
Here k=2, i=1, j=2.
Left[i] <= Right[j] -> condition True.
Therefore A[k] = Left[i] -> A[2] = Left[1].
i will be incremented.
Iteration 3:-
Here k=3, i=2, j=2.
Left[i] <= Right[j] -> condition True.
Therefore A[k] = Left[i] -> A[3] = Left[2].
i will be incremented.
Iteration 4:-
Here k=4, i=3, j=2.
Left[i] <= Right[j] -> condition false.
Therefore A[k] = Right[j] -> A[4] = Right[2].
j will be incremented.
Iteration 5:-
Here k=5, i=3, j=3.
Left[i] <= Right[j] -> condition false.
Therefore A[k] = Right[j] -> A[5] = Right[3].
j will be incremented.
Iteration 6:-
Here k=6, i=3, j=4.
Left[i] <= Right[j] -> condition True.
Therefore A[k] = Left[i] -> A[6] = Left[3].
i will be incremented.
Iteration 7:-
Here k=7, i=4, j=4.
Left[i] <= Right[j] -> condition false.
Therefore A[k] = Right[j] -> A[7] = Right[3].
j will be incremented.
Iteration 8:-
Here k=8, i=4, j=5.
Left[i] <= Right[j] -> condition True.
Therefore A[k] = Left[i] -> A[8] = Left[4].
i will be incremented.
Iteration 9:-
(k > r). Therefore loop will terminate and we will get a complete sorted merged array.
Merge Sort Example implementation in C++:-
I will provide very soon Merge Sort C++ implementation code.
Running time of C++ Merge Sort:-
In all three worst, average and best case, C++ merge sort running time is nlogn.
Things to remember:-
- All the functions and operations are performed on the indexes, some people get confused and think we are storing values in variables, but remember that we are not storing values anywhere, we are performing all the operation on the indexes of our given array.
If you have any questions, then ask them on our forum or make a comment on this post.
