/* Program to implement Merge Sort */
/* Input:Unsorted Array
Output:Sorted Array */
import java.io.DataInputStream; // to load DataInputStream class
import java.util.*;
class MergeSort
{
public static void main(String args[ ])
{
int i,n=0;
int increments[]={5,3,1};
System.out.println("Enter the size of the array:");
Scanner src=new Scanner (System.in);
int w=src.nextInt();
int x[]=new int[w];
DataInputStream in = new DataInputStream(System.in);
try
{
System.out.print("Enter how many numbers to be sorted : ");
n = Integer.parseInt(in.readLine());
System.out.println("Enter "+n+" numbers in any order....");
for(i=0;i<n;i++)
{
System.out.print("\t\tElement x["+(i+1)+"]=");
x[i] = Integer.parseInt(in.readLine());
}
}
catch(Exception e) { System.out.println("I/O Error"); }
merge(x,n); // Call to Merge Sort
System.out.println("\nSorted Elements are :");
for(i=0;i<n;i++)
System.out.println("\t\tElement x["+(i+1)+"]="+x[i]);
}
//Merge Sort Function
static void merge(int x[],int n)
{
int sub[] = new int[25];
int i,j,k,l1,l2,u1,u2,size;
size=1; //Merge files of size 1
while(size<n)
{
l1=0; // Initialize lower bounds of first file
k=0; // k is index for auxiliary array
while((l1+size)<n) // Check to see if there are two files to merge
{
l2=l1+size; // Compute remaining indices
u1=l2-1;
u2=((l2+size-1)<n)?(l2+size-1):(n-1);
// Proceed through the two subfiles
for(i=l1,j=l2;i<=u1 && j<=u2;k++)
if(x[i]<=x[j])
sub[k]=x[i++];
else
sub[k]=x[j++];
/*At this point, one of the subfiles has been exhausted. Insert any remaining portions of the other file*/
for(;i<=u1;k++)
sub[k]=x[i++];
for(;j<=u2;k++)
sub[k]=x[j++];
// Advance l1 to the start of the next pair of files.
l1=u2+1;
} // end of while
//Copy any remaining single file
for(i=l1;k<n;i++)
sub[k++]=x[i];
//Copy aux into x and adjust size
for(i=0;i<n;i++)
x[i]=sub[i];
size*=2;
} // end of while
} // end of merge sort function
}
OUTPUT
=========================================================================
C:\Program Files\Java\jdk1.7.0_02\bin>javac MergeSort.java
Note: MergeSort.java uses or overrides a deprecated API.
Note: Recompile with -Xlint:deprecation for details.
C:\Program Files\Java\jdk1.7.0_02\bin>java MergeSort
Enter the size of the array:
5
Enter how many numbers to be sorted : 5
Enter 5 numbers in any order....
Element x[1]=354
Element x[2]=224
Element x[3]=39
Element x[4]=447
Element x[5]=21
Sorted Elements are :
Element x[1]=21
Element x[2]=39
Element x[3]=224
Element x[4]=354
Element x[5]=447
No comments:
Post a Comment