Create a mergeSort class that contains a Sort method and a M

Create a mergeSort class that contains a Sort method and a Main method that calls this sort method using the sequence in (3, 1, 4, 1, 5, 9, 2, 6, 5).

Solution

Hi, Please find my program.

Please let me know in case of any issue.

/* Java program for Merge Sort */

public class MergeSort

{

   // Merges two subarrays of arr[].

   // First subarray is arr[l..m]

   // Second subarray is arr[m+1..r]

   public void merge(int arr[], int l, int m, int r)

   {

       // Find sizes of two subarrays to be merged

       int n1 = m - l + 1;

       int n2 = r - m;

       /* 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] = arr[l + i];

       for (int j=0; j<n2; ++j)

           R[j] = arr[m + 1+ j];

       /* Merge the temp arrays */

       // Initial indexes of first and second subarrays

       int i = 0, j = 0;

       // Initial index of merged subarry array

       int k = l;

       while (i < n1 && j < n2)

       {

           if (L[i] <= R[j])

           {

               arr[k] = L[i];

               i++;

           }

           else

           {

               arr[k] = R[j];

               j++;

           }

           k++;

       }

       /* Copy remaining elements of L[] if any */

       while (i < n1)

       {

           arr[k] = L[i];

           i++;

           k++;

       }

       /* Copy remaining elements of L[] if any */

       while (j < n2)

       {

           arr[k] = R[j];

           j++;

           k++;

       }

   }

   // Main function that sorts arr[l..r] using

   // merge()

   public void sort(int arr[], int l, int r)

   {

       if (l < r)

       {

           // Find the middle point

           int m = (l+r)/2;

           // Sort first and second halves

           sort(arr, l, m);

           sort(arr , m+1, r);

           // Merge the sorted halves

           merge(arr, l, m, r);

       }

   }

   /* A utility function to print array of size n */

   void printArray(int arr[])

   {

       int n = arr.length;

       for (int i=0; i<n; ++i)

           System.out.print(arr[i] + \" \");

       System.out.println();

   }

   // Driver method

   public static void main(String args[])

   {

       int arr[] = {3, 1, 4, 1, 5, 9, 2, 6, 5};

      

       MergeSort mergerSort = new MergeSort();

       System.out.println(\"Given Array\");

       mergerSort.printArray(arr);

       mergerSort.sort(arr, 0, arr.length-1);

       System.out.println(\"\ Sorted array\");

       mergerSort.printArray(arr);

   }

}

/*

Sample run:

Given Array

3 1 4 1 5 9 2 6 5

Sorted array

1 1 2 3 4 5 5 6 9

*/