Explore
ProGrad Programs
Placement Prep
TCS Codevita
Live Placement Training
Live Aptitude Training
Live Programming Training
Webinars
About Us

Edit
Reply




Edit

Algorithm of Merge Sort in C, C++, Java with Examples | FACE Prep

Published on 12 Mar 2020

In this article, we will be discussing Merge sort in C, C++ and Java.So far we have discussed some of the sorting algorithms like Bubble, Selection and Insertion sort. If you observe, all these algorithms are equally inefficient.


In Bubble and Selection sort, we need to traverse the same array many times. Insertion sort is pretty good if most of the array elements are already sorted. But if not, then the same situation occurs. However, Merge sort will be completely different from those and let us see how.


What is Merge Sort Algorithm?


In Merge sort, the given array is sorted using Divide and Conquer algorithm. This algorithm divides the input array into sub-arrays (until each sub array contains one element only) and then recursively sorts the sub-arrays. The sorted sub-arrays are then merged back together to form a single sorted array. This is where Merge sort differs from all other sorting algorithms.


A simple visualization of this is shown below.


merge sort in c


Merge Sort Pseudo Code


procedure merge(array, start, mid, end) 
num1 = mid - start + 1
num2 = end - mid

// Copy data to temporary arrays arr1[] and arr2[] 
for i = 0 to num1
arr1[i] = arr[start + i] 
for j = 0 to num2
arr2[j] = arr[mid + 1 + j]

// Merge the temp arrays back into arr[]
i = 0 // Initial index of first subarray 
j = 0 // Initial index of second subarray 
k = start // Initial index of merged subarray 
while (i < num1 and j < num2) 
if (arr1[i] <= arr2[j]) then
arr[k] = arr1[i] 
i++
end if 
else
arr[k] = arr2[j]
j++ 
end else 
k++ 
end while 

// Copy the remaining elements of arr1[], if there are any 
while (i < num1) 
arr[k] = arr1[i] 
i++ 
k++
end while

// Copy the remaining elements of arr2[], if there are any
while (j < num2) 
arr[k] = arr2[j] 
j++ 
k++ 
end while 
end procedure 

procedure divide(array, start, end)
if(start < end) then
mid = (start + end) / 2
divide(arr, start, mid)
divide(arr, mid + 1, end)
merge(arr, start, mid, end)
end if
end procedure


Merge Sort in C, C++, Java


Here is the implementation of Merge sort in C, C++ and Java. This implementation is explained with a suitable example in detail below.


C
C++
Java

Output
Input- 4 8 13 2 23 16 Output- 2 4 8 13 16 23


Example of Merge Sort


Let us consider an array A={4, 8, 13, 2, 23, 16}. The working of Merge sort for this array of elements is shown below.



merge sort in c

Merge Sort Time Complexity


Here the array consists of 6 elements. So, the number of sub-arrays formed with a single element in it is 6. Then those 6 sub-arrays are merged to 4 sub-arrays. To do this we need 6 append (adding of elements) operations.


Append operation: Comparing the elements and inserting them in sorted order.


Then those 4 sub-arrays are merged to 2 sub-arrays. Again here comes another 6 append operations.


Then those 2 sub-arrays to 1 single sorted array. Another 6 append operations required to do this.


Total 6 + 6+ 6 = 18 append operations. This is the total complexity of the entire merge sort. If the number of array elements keeps increasing, then append operations will also increase. So, in general, total complexity can be (n * log n)


Check out more Data Structure Programming Questions


Also See Similar DS Sorting Techniques


If you have any feedback about this article and want to improve this, please write to enquiry@faceprep.in