Merge Sort in C++ with examples

1

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.

Merge Sort1

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.

Merge Sort2

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.

Merge Sort3

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.

Merge Sort4

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:-

Merge Sort5

Left[i] <= Right[j] -> condition false.

Therefore A[k] = Right[j] -> A[1] = Right[1].

j will be incremented.

Merge Sort6

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.

Merge Sort7

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.

Merge Sort8

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.

Merge Sort9

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.

Merge Sort10

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.

Merge Sort11

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.

Merge Sort12

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.

Merge Sort13

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.

4.2/5 - (4 votes)

Author

  • royal52

    I’m a DevSecOps Software engineer by profession and a SEO hobbyist. I’m passionate about everything Software, including game development.

I’m a DevSecOps Software engineer by profession and a SEO hobbyist. I’m passionate about everything Software, including game development.

We will be happy to hear your thoughts

Leave a Reply