Question

Please use Java

You have to write a programing for the following sorting algorithms in increasing order and print required steps in order to explain how your sorting algorithms work.

3. Implement the merge sort algorithm.

With answers in this link (https://www.chegg.com/homework-help/questions-and-answers/write-programing-following-sorting-algorithms-increasing-order-print-required-steps-order--q53916147?trackid=PJ_TOK85), answer the above questions.

Answer 1

Solution:

import java.util.*;
//Java program for merge sort
class Main {
   //Implemented for merging two subarrays
   //first subarray starts from p and end at q
   //second one start from q and end at r
   void merge_arr(int ar[], int p, int q, int r)
   {
   int i,j;
       // Finding the size of two arrays thar are required to be merged
       int n1 = q - p + 1;
       int n2 = r - q;

       //creating a temporary array
       int P[] = new int[n1];
       int R[] = new int[n2];

       //copying the data of two array to array L and R
       for (i = 0; i < n1; ++i)
           P[i] = ar[p + i];
       for (j = 0; j < n2; ++j)
           R[j] = ar[q + 1 + j];

       i = 0;
       j = 0;

   //looping through the element and comparing
       int k = p;
       while (j < n2 && i < n1) {
       //If in array p the element at index i is less than the element in R at index j
           if (P[i] <= R[j]) {
           //then keeping that element in ar at index k
               ar[k] = P[i];
               //incrementing i for the next value
               i++;
           }
           else {
           //otherwise element from array R at index j is stored in ar at index k
               ar[k] = R[j];
               //incrementing j for next value
               j++;
           }
           //incrementing k to store value at next position
           k++;
       }

       //adding remaining value from array P if any left
       while (i < n1) {
           ar[k] = P[i];
           i++;
           k++;
       }

       //adding remaining elements from array R if any left
       while (j < n2) {
           ar[k] = R[j];
           j++;
           k++;
       }
   }

   //function to sort each half of array
   void M_sort(int arr[], int p, int r)
   {
       if (p < r) {
           // Finding mid point
           int mid = (p + r) / 2;

           // Sorting the first halve of array
           M_sort(arr, p, mid);
           //sorting the second halve of array
           M_sort(arr, mid + 1, r);
//merging the two halves after sorting
           merge_arr(arr, p, mid, r);
       }
   }

   //function to print the resultant array
   static void print_Array(int ar[])
   {
       int n = ar.length,i;
       for (i = 0; i < n; ++i)
       {
           System.out.print(ar[i] + " ");
       }
       System.out.println("\n");
   }

   // Driver code
   public static void main(String args[])
   {
       int i,n;
       Scanner s = new Scanner(System.in);
System.out.print("Enter number of elements in array:");
//Taking number of elements in array as input from user
n = s.nextInt();
int ar[] = new int[n];
System.out.println("Enter elements of array:");
//Taking array elements as input from user
for( i = 0; i < n; i++)
{
ar[i] = s.nextInt();
}

       System.out.println("Array before sorting :");
       print_Array(ar);
//object of class Main created
       Main obj = new Main();
       //M_sort is called to sort the ARRAY ar
       obj.M_sort(ar, 0, ar.length - 1);

       System.out.println("Array after sorting :");
       //calling function print_Array to print the sorted array
       print_Array(ar);
   }
}

Steps to solve :

• Merge sort is based on divide and conquer approach
• Firstly given array is divided in to two half from the middle of array
• now to sort the first half of array M_sort () is called which again divided the first half from middle
• This process take place in same way for second half of array and repeats until the array of single element formed
• then the elements of array are sorted
• now these array are merged together to get the resultant array

Note : if you find any error in the above code it may be due to different name of your file than the class name ,so please make sure that you save your file with name Main.java.

If you find my answer helpful please give thumbs up .Thank you