Question

USING JAVA

Almost sort the array using Merge Sort. Perform Merge Sort as usual except that during the final merge, it is not necessary to merge all n elements, but only the elements in positions 1 to k.

Answer 1

Java code:

import java.util.Scanner;
public class MergeSort{

//merge function
public static void merge(int arr[],int left,int mid,int right)
{
int i,j,k;
int sz1=mid-left+1;
int sz2=right-mid;
int L[]=new int[sz1];
int R[]=new int[sz2];
for (i = 0;i<sz1;i++)
{
   L[i]=arr[left+i];
   }
for (j = 0;j<sz2;j++)
{
   R[j]=arr[mid+1+j];
   }
  
  
  
i = 0;
j = 0;
k = left;
while (i<sz1 && j<sz2)
{
if (L[i] <= R[j])
{
arr[k]=L[i];
i++;
}
else
{
arr[k]=R[j];
j++;
}
k++;
  
}
  
while(i<sz1)
{
arr[k]=L[i];
i++;
k++;
}
while(j<sz2)
{
arr[k]=R[j];
j++;
k++;
}
  
}

//merge sort function
public static void mergeSort(int arr[],int left,int right)
{

if(left<right)
{
int mid=left+(right-left)/2;
mergeSort(arr,left,mid);
mergeSort(arr,mid+1,right);
merge(arr,left,mid,right);
}

  
}

//main function
public static void main(String[] args) {
   int data[]=new int[100];
   int n,k,i;
   Scanner scan = new Scanner(System.in);

   System.out.print("Enter number of items in array: ");
   n=scan.nextInt(); //store total number of items in array in variable n
   System.out.print("Enter array items: ");
   for(i=0;i<n;i++)
   {
       data[i]=scan.nextInt();   //stored input array items in array
   }
   System.out.print("Enter value of k: ");
   k=scan.nextInt(); //enter position after which array is sorted

   System.out.println("Initial array elements: ");
   for(i=0;i<n;i++)
   {
       System.out.print(data[i]+" ");
   }
  

   mergeSort(data,0,k-1); //call mergesort for the array from oth position to k-1

   System.out.println("\nArray after selection sort: ");
   for(i=0;i<n;i++)
   {
       System.out.print(data[i]+" ");
   }
}

}

Output: