Java public cts Node t next ni next SolutionYou have to crea

Java

public cts Node t next ni next

Solution

You have to create two class file in same package.

First Class File :

package mergesortdemo;

import java.util.*;

public class MergesortDemo
{
  
public static void merge(int [] A, int first_var, int last_var)
{
     
       int [] temp_var = new int[last_var-first_var+1];
       if (first_var<last_var)
{
           int i1 = first_var;
           int mid_var = (first_var+last_var)/2;
           int i2 = mid_var+1;
                      
           for(int i=0;i< temp_var.length;i++)
{
               if (i1>mid_var)
{
                   temp_var[i]= A[i2];
                   i2++;
               }              
               else
                   if (i2>last_var)
{
                       temp_var[i]= A[i1];
                       i1++;
                   }
                   else
                       if (A[i1]<A[i2])
{
                           temp_var[i]= A[i1];
                           i1++;
                       }
                       else
{
                           temp_var[i]= A[i2];
                           i2++;
                       }
          
           }
           for(int i=0;i<temp_var.length;i++)
               A[first_var+i]=temp_var[i];
       }
   }

   public static void mergesort(int [] A)
{
       Stack<MergesortRecord> stack=new Stack();
       MergesortRecord m = new MergesortRecord(false, 0, A.length-1);
       stack.push(m);
       while (!stack.empty())
{
          
           System.out.println(\"Stack size is: \" + stack.size());
           System.out.print(\"Top of stack is: \");
           stack.peek().print();
                  
           m=stack.pop();
           if (m.getsorted())
{
               merge(A,m.getfirst(),m.getlast());
           }
           else{
               if (m.getfirst()<m.getlast())
{
                   int mid_var = (m.getfirst()+m.getlast())/2;
                   stack.push(new MergesortRecord(true,m.getfirst(),m.getlast()));
                   stack.push(new MergesortRecord(false,m.getfirst(),mid_var));
                   stack.push(new MergesortRecord(false,mid_var+1,m.getlast()));
               }
           }
           System.out.print(\"Current array is: \");
           Array_print(A);   
           System.out.println();
       }
   }
  
  
   public static void Array_print(int [] A){
       for(int i =0;i<A.length;i++)
           System.out.print(A[i]+\" \");
       System.out.println();
   }
  
   public static void main(String[] args)
{
       int [] A = {13,2,45,12,9,10,67,5,90,-3};
       mergesort(A);
          
   }
}

Second Class File :

package mergesortdemo;
import java.util.*;

public class MergesortRecord {
private boolean sorted; //Indicates if the first and second half of the array have already been sorted
   private int first_var;
   private int last_var;
  
   public MergesortRecord(boolean s, int f, int l){
       sorted = s;
       first_var = f;
       last_var = l;
   }

   public int getfirst() {
           return first_var;
   }
  
   public boolean getsorted() {
           return sorted;
   }
  
   public int getlast() {
           return last_var;
   }
  
   public void print(){
       System.out.println(sorted+\" \"+first_var+\" \"+last_var);
   }
  
}

Output:

run:
Stack size is: 1
Top of stack is: false 0 9
Current array is: 13 2 45 12 9 10 67 5 90 -3

Stack size is: 3
Top of stack is: false 5 9
Current array is: 13 2 45 12 9 10 67 5 90 -3

Stack size is: 5
Top of stack is: false 8 9
Current array is: 13 2 45 12 9 10 67 5 90 -3

Stack size is: 7
Top of stack is: false 9 9
Current array is: 13 2 45 12 9 10 67 5 90 -3

Stack size is: 6
Top of stack is: false 8 8
Current array is: 13 2 45 12 9 10 67 5 90 -3

Stack size is: 5
Top of stack is: true 8 9
Current array is: 13 2 45 12 9 10 67 5 -3 90

Stack size is: 4
Top of stack is: false 5 7
Current array is: 13 2 45 12 9 10 67 5 -3 90

Stack size is: 6
Top of stack is: false 7 7
Current array is: 13 2 45 12 9 10 67 5 -3 90

Stack size is: 5
Top of stack is: false 5 6
Current array is: 13 2 45 12 9 10 67 5 -3 90

Stack size is: 7
Top of stack is: false 6 6
Current array is: 13 2 45 12 9 10 67 5 -3 90

Stack size is: 6
Top of stack is: false 5 5
Current array is: 13 2 45 12 9 10 67 5 -3 90

Stack size is: 5
Top of stack is: true 5 6
Current array is: 13 2 45 12 9 10 67 5 -3 90

Stack size is: 4
Top of stack is: true 5 7
Current array is: 13 2 45 12 9 5 10 67 -3 90

Stack size is: 3
Top of stack is: true 5 9
Current array is: 13 2 45 12 9 -3 5 10 67 90

Stack size is: 2
Top of stack is: false 0 4
Current array is: 13 2 45 12 9 -3 5 10 67 90

Stack size is: 4
Top of stack is: false 3 4
Current array is: 13 2 45 12 9 -3 5 10 67 90

Stack size is: 6
Top of stack is: false 4 4
Current array is: 13 2 45 12 9 -3 5 10 67 90

Stack size is: 5
Top of stack is: false 3 3
Current array is: 13 2 45 12 9 -3 5 10 67 90

Stack size is: 4
Top of stack is: true 3 4
Current array is: 13 2 45 9 12 -3 5 10 67 90

Stack size is: 3
Top of stack is: false 0 2
Current array is: 13 2 45 9 12 -3 5 10 67 90

Stack size is: 5
Top of stack is: false 2 2
Current array is: 13 2 45 9 12 -3 5 10 67 90

Stack size is: 4
Top of stack is: false 0 1
Current array is: 13 2 45 9 12 -3 5 10 67 90

Stack size is: 6
Top of stack is: false 1 1
Current array is: 13 2 45 9 12 -3 5 10 67 90

Stack size is: 5
Top of stack is: false 0 0
Current array is: 13 2 45 9 12 -3 5 10 67 90

Stack size is: 4
Top of stack is: true 0 1
Current array is: 2 13 45 9 12 -3 5 10 67 90

Stack size is: 3
Top of stack is: true 0 2
Current array is: 2 13 45 9 12 -3 5 10 67 90

Stack size is: 2
Top of stack is: true 0 4
Current array is: 2 9 12 13 45 -3 5 10 67 90

Stack size is: 1
Top of stack is: true 0 9
Current array is: -3 2 5 9 10 12 13 45 67 90

BUILD SUCCESSFUL (total time: 0 seconds)