Question

Java program to implement the merge sort your own and test it to sort a list of names based on the frequency.

Answer 1

import java.io.*;
import java.util.*;
public class Main
{
////// main function as tester function ///////
   public static void main(String[] args) {

       int n = 5; /// size of list
       Name[] arr = new Name[n]; /// array if Name objects

////// adding names and corresponding frequencies /////
       arr[0] = new Name("apple", 10);
       arr[1] = new Name("orange", 8);
       arr[2] = new Name("banana", 1);
       arr[3] = new Name("potato", 4);
       arr[4] = new Name("onion", 0);
  
//// calling sorting function /////
       mergeSort(arr, n);
  
  
////// printing the sorted array of Name objects based on frequency
       for(int i = 0;i<n;i++)
       {
           System.out.println(arr[i].name + " ---- " + arr[i].frequency);
       }
   }

   public static void mergeSort(Name[] arr, int n)
   {
       if(n<2) return; //// base condition to terminate the recursion
      
       int mid = n/2;
      
       //////// division of array into 2 arrays //////
       Name[] L = new Name[mid];
       Name[] R = new Name[n-mid];
  
int i = 0;
       for(i = 0;i<mid;i++)
       {
           L[i] = arr[i];
       }

       for(int j = 0;j<n-mid;j++)
       {
           R[j] = arr[i];
           i++;
       }

  
///// recursively sorting the splited arrays
       mergeSort(L, mid);
       mergeSort(R, n-mid);
  
///// merging the splited arrays to final sorted array
       merge(L, R, arr);
   }
  
  
//////////// merge logic //////////////
   public static void merge(Name[] L, Name[] R, Name[] arr)
   {
       int l = L.length;
       int r = R.length;
       int n = arr.length;

       int i = 0;
       int j = 0;
       int k = 0;

       while(i<l && j<r && k<n)
       {
           if(L[i].frequency < R[j].frequency)
           {
               arr[k] = L[i];
               i++;
           }
           else
           {
               arr[k] = R[j];
               j++;
           }

           k++;
       }

       while (i<l && k<n)
       {
           arr[k] = L[i];
           i++;
           k++;
       }

       while (j<r && k<n)
       {
           arr[k] = R[j];
           j++;
           k++;
       }
   }

}

////// name class which contains name and the frequency of corresponding name
class Name
{
   String name;
   int frequency;

   public Name(String name, int frequency)
   {
       this.name = name;
       this.frequency = frequency;
   }
}