/* Java program for Merge Sort using copyOf method*/
import java.util.*;
class msrk
{
static void sort(int a[], int p, int r)
{
if (p < r)
{
// Find the middle point
int q = (p+r)/2;
// Sort first and second halves
sort(a, p, q);
sort(a , q+1, r);
// Merge the sorted halves
merge(a, p, q, r);
System.out.printf("\n merged array element :");
int[] FS = Arrays.copyOf(a,r+1);
for (int k=0; k<FS.length; k++)
System.out.print(FS[k]+" ");
}
}
public static void main(String args[])
{
int a[] = {38,27,43,3,9,82,10};
int n = a.length;
System.out.printf("\n unsorted array :");
for (int i=0; i<n; i++)
System.out.print(a[i]+" ");
sort(a, 0, n-1);
System.out.printf("\n sorted array :");
for (int i=0; i<n; i++)
System.out.print(a[i]+" ");
}
static void merge(int a[], int p, int q, int r)
{
// Find sizes of two subarrays to be merged
int n1 = q-p+1 ;
int n2 = r-q; // r-(q+1)+1 r-q-1+1
/* Create temp arrays */
int L[] = new int [n1];
int R[] = new int [n2];
/*Copy data to temp arrays*/
for (int i=0; i<n1; ++i)
L[i] = a[p + i];
for (int j=0; j<n2; ++j)
R[j] = a[q + 1 + j];
/* Merge the temp arrays */
// Initial indexes of first and second subarrays
int i = 0, j = 0;
// Initial index of merged sub array
int k = p;
while (i < n1 && j < n2)
{
a[k++]=(L[i] <= R[j]) ? L[i++] : R[j++];
}
/* Copy remaining elements of L[] if any */
while (i < n1)
{
a[k] = L[i];
i++;
k++;
}
/* Copy remaining elements of R[] if any */
while (j < n2)
{
a[k] = R[j];
j++;
k++;
}
}
}
output:
import java.util.*;
class msrk
{
static void sort(int a[], int p, int r)
{
if (p < r)
{
// Find the middle point
int q = (p+r)/2;
// Sort first and second halves
sort(a, p, q);
sort(a , q+1, r);
// Merge the sorted halves
merge(a, p, q, r);
System.out.printf("\n merged array element :");
int[] FS = Arrays.copyOf(a,r+1);
for (int k=0; k<FS.length; k++)
System.out.print(FS[k]+" ");
}
}
public static void main(String args[])
{
int a[] = {38,27,43,3,9,82,10};
int n = a.length;
System.out.printf("\n unsorted array :");
for (int i=0; i<n; i++)
System.out.print(a[i]+" ");
sort(a, 0, n-1);
System.out.printf("\n sorted array :");
for (int i=0; i<n; i++)
System.out.print(a[i]+" ");
}
static void merge(int a[], int p, int q, int r)
{
// Find sizes of two subarrays to be merged
int n1 = q-p+1 ;
int n2 = r-q; // r-(q+1)+1 r-q-1+1
/* Create temp arrays */
int L[] = new int [n1];
int R[] = new int [n2];
/*Copy data to temp arrays*/
for (int i=0; i<n1; ++i)
L[i] = a[p + i];
for (int j=0; j<n2; ++j)
R[j] = a[q + 1 + j];
/* Merge the temp arrays */
// Initial indexes of first and second subarrays
int i = 0, j = 0;
// Initial index of merged sub array
int k = p;
while (i < n1 && j < n2)
{
a[k++]=(L[i] <= R[j]) ? L[i++] : R[j++];
}
/* Copy remaining elements of L[] if any */
while (i < n1)
{
a[k] = L[i];
i++;
k++;
}
/* Copy remaining elements of R[] if any */
while (j < n2)
{
a[k] = R[j];
j++;
k++;
}
}
}
output:
No comments:
Post a Comment