Java Program to Implement Merge Sort

What is Merge Sort?

Merge Sort in Java is a divide and conquer-based sorting algorithm. In this sorting algorithm the unsorted array keeps on dividing into two halves until the array is either empty or contains only one element, which is the base case of Merge Sort, and then the halves are combined/Merged in sorted order producing a sorted array. It is one of the most popular and efficient sorting techniques.

Merge Sort Algorithm
Start
1. Declare Array, left, right and mid variables
2. Find mid by formula mid = (left+right)/2
3. Call MergeSort for the left to mid
4. Call MergeSort for mid+1 to right
5. Continue step 2, 3, and 4 while the left is less than the right
6. Then Call the Merge function
End
Problem Description

Write a Java Program to Implement Merge Sort on n Numbers Without tail-recursion.

Problem Solution

Divide the array into two equal parts. Recursively sort the two parts of the array and finally merge them.

Example:

Merge Sort Example

advertisement
advertisement
Program/Source Code

Here is the source code of the Java Program to Implement Merge Sort on n Numbers Without tail-recursion. The program is successfully compiled and tested using IDE IntelliJ Idea in Windows 7. The program output is also shown below.

  1.  
  2. //Java Program to Implement Merge Sort on n Numbers Without tail-recursion
  3.  
  4. import java.io.BufferedReader;
  5. import java.io.InputStreamReader;
  6. import java.util.Arrays;
  7.  
  8. public class MergeSort {
  9.     // Function to merge the two sorted arrays
  10.     static void merge(int[] array,int low,int mid,int high){
  11.         int i,j,k;
  12.         int[] c= new int[high-low+1];
  13.         k = 0;
  14.         i=low;
  15.         j=mid+1;
  16.         while(i<=mid && j<=high){
  17.             if(array[i]<=array[j]){
  18.                 c[k++] = array[i++];
  19.             }
  20.             else{
  21.                 c[k++] = array[j++];
  22.             }
  23.         }
  24.         while(i<=mid){
  25.             c[k++] = array[i++];
  26.         }
  27.         while(j<=high){
  28.             c[k++] = array[j++];
  29.         }
  30.         k=0;
  31.         for(i = low; i<=high; i++){
  32.             array[i] = c[k++];
  33.         }
  34.     }
  35.     // Function implementing the merge sort
  36.     static void mergeSort(int[] array,int low, int high){
  37.         if(high-low+1>1){
  38.             int mid = (low+high)/2;
  39.             mergeSort(array,low,mid);
  40.             mergeSort(array,mid+1,high);
  41.             merge(array,low,mid,high);
  42.         }
  43.     }
  44.     // Function to read the input and display the output
  45.     public static void main(String[] args) {
  46.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  47.         int size;
  48.         System.out.println("Enter the size of the array");
  49.         try {
  50.             size = Integer.parseInt(br.readLine());
  51.         } catch (Exception e) {
  52.             System.out.println("Invalid Input");
  53.             return;
  54.         }
  55.         int[] array = new int[size];
  56.         System.out.println("Enter array elements");
  57.         int i;
  58.         for (i = 0; i < array.length; i++) {
  59.             try {
  60.                 array[i] = Integer.parseInt(br.readLine());
  61.             } catch (Exception e) {
  62.                 System.out.println("An error Occurred");
  63.             }
  64.         }
  65.         System.out.println("The initial array is");
  66.         System.out.println(Arrays.toString(array));
  67.         mergeSort(array,0,array.length-1);
  68.         System.out.println("The sorted array is");
  69.         System.out.println(Arrays.toString(array));
  70.     }
  71. }
Program Explanation

1. In function mergeSort(), first, we check if there is more than one element in the array, through the condition if(high-low+1>1).
2. If that is the case, a recursive call is made on the two halves obtained by dividing the array.
3. In function merge(), the while(i<=mid && j<=high) loop merges the elements of the two array into the new array c.
4. The loops while(i<=mid) and while(j<=high), adds any remaining elements of the arrays, at the end of c.

Note: Join free Sanfoundry classes at Telegram or Youtube

Time Complexity: O(n*log(n))
Time Complexity of Merge Sort is O(nlogn) for best, average, and worst case. Where n is the number of elements in the array.

Space Complexity: O(n)
Space Complexity of Merge Sort using an array is O(n), because Merge Sort requires an Auxiliary/temporary array for copying the elements.

Runtime Test Cases

Test Case 1: Here, the elements are reverse sorted.

 
Enter the size of the array
5
Enter array elements
5
4
3
2
1
The initial array is
[5, 4, 3, 2, 1]
The sorted array is
[1, 2, 3, 4, 5]

Test Case 2: Here, the elements are entered in random order.

advertisement
 
Enter the size of the array
8
Enter array elements
7
2
3
10
1
0
6
9
The initial array is
[7, 2, 3, 10, 1, 0, 6, 9]
The sorted array is
[0, 1, 2, 3, 6, 7, 9, 10]

Advantages of Merge Sort Algorithm:

  • Merge sort is an efficient sorting algorithm in Java, with an average and worst-case time complexity of O(n log n).
  • Merge sort has a simple and elegant recursive implementation, making it easy to understand and implement in Java.
  • Merge sort uses the divide and conquer technique, which reduces the problem into smaller subproblems until they can be solved directly.
  • Merge sort has a space complexity of O(n), making it suitable for sorting large datasets without running out of memory.
  • Merge sort is a stable sorting algorithm, which preserves the relative order of equal elements in the input array.
  • Merge sort is suitable for sorting complex data structures such as arrays of objects or strings.

Drawbacks:

advertisement
  • For Small datasets merge sort is slower than other algorithms such as selection or insertion sort.
  • It requires additional space of O(n).
  • Even if the array is sorted Merge Sort will run completely.

To practice programs on every topic in Java, please visit “Programming Examples in Java”, “Data Structures in Java” and “Algorithms in Java”.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.