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

«
»

This is the Java Program to Implement Merge Sort on n Numbers Without tail-recursion.

Problem Description

Given an array of integers, sort the array using merge sort algorithm.

Problem Solution

The idea is to divide the array into two equal parts. Recursively sort the two parts of the array and finally merge them.

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.

advertisement
advertisement

Time Complexity: O(n*log(n)) where n is the number of elements in the array.

Runtime Test Cases
 
Case 1 (Simple Test Case):
 
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]
 
Case 2 (Simple Test Case - another example):
 
Enter the size of the array
8
Enter array elements
4
3
2
1
1
2
3
4
The initial array is
[4, 3, 2, 1, 1, 2, 3, 4]
The sorted array is
[1, 1, 2, 2, 3, 3, 4, 4]

Sanfoundry Global Education & Learning Series – Java Programs.

advertisement

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!
advertisement
advertisement
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn | Youtube | Instagram | Facebook | Twitter