How to write Merge sort program in Java ?

By | July 20, 2020

In this post, we will learn How to write a Merge sort program in Java?

Merge sort is very much efficient than the simple sorting algorithms like the bubble sort, selection sort, and insertion sort. the only drawback is that it requires an additional array along with the input array that is sorted.

How to merge sort works

Merge sort is usually working on the concept of merging two sorted arrays to create another array which is also sorted.

Now the question is that how do we get sorted arrays which are merged?

Since the merge sort follows the divide and conquer algorithm so here the idea is to divide the input array into two halves then each of these halves is also further divided into halves and so on until we get sub-arrays with only one element which is considered a sorted array.

At that point we start merging these sub-arrays from two single element sub-arrays then we create a sorted merged array of two elements. Then two such sorted sub-arrays of two elements are merged and create a sorted array of four elements and so on until you have a sorted array of all the elements.

Since in this algorithm array is recursively divided into two halves so this division process can be written as a recursive method where the base case becomes the point when we have sub-arrays with only one element each.

To Understand Merge sort, let us walk through an example.

Input Array

We know that the merge sort first divides the whole array iteratively into equal halves unless the atomic values are achieved. We see here that an array of 8 items is divided into two arrays of size 4.

This does not change the sequence of appearance of items in the original array, now we divide these two arrays into halves.

                          

We further divide these arrays and we achieve atomic values that can no more be divided.

 Now, we combine them in exactly the same manner as they were broken down

We first compare the element for each array and then combine them into another array in a sorted manner. we see that 54 and 26  in the target array of 2 values we put 26 first followed by 54

 Similarly, we compared 93 and 17 and in the target array of 2 values, we put 17 first followed by 93. On similar lines. We change the order of 77 and 31 whereas 44 and 55 are placed sequentially.

In the next iteration of the combining phase, we compare lists of two data values and merge them into an array of found data values placing all in sorted order.

After the final margin, the array should look like this:

The overall flow of the above discussion can be depicted as:

Merge Sort

 

Source code: 

The output of this program: 

Array is sorted using Merge Sort
17 26 31 44 54 55 77 93

Performance of merge sort:

In merge sort usually, there is a sub-division of arrays and for each sub-division, there is merging. Number of levels (subdivisions of the array) can be calculated as– (log n + 1)

For example, log of 8 base 2 is 3, so log8 + 1 = 4

Which is equivalent to the number of halves for the array having 8 elements– 8 4 2 1.

At each level N elements are merged which makes the time complexity of merge sort as n*(log n + 1). we can discard the 1 so the time complexity of merge sort is O(n log n).

Merge sort is not an “in-place” sorting algorithm because it requires extra space and auxiliary space required is equal to the number of elements in the original array so the space complexity of merge sort is O(n).

You May Also Like:

What is Sorting and why is Sorting Necessary?
Classification of Sorting Algorithms
Java program for Bubble Sort using Iterative Approach
Java program for Bubble Sort using recursive Approach
How to Write a Java program for Selection Sort in Java
How to Write a Java program for Insertion Sort in java?
Tree Sort Using Binary Search Tree in Java

That’s all about How to write a Merge sort program in Java?
If you have any feedback or suggestion please feel free to drop in below comment box.

Leave a Reply

Your email address will not be published.