Link copied to clipboard. Share away!

Dismiss

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**.

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.**

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

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

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**.

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

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

×