The implementation for Mergesort given in Section 74 takes a

The implementation for Mergesort given in Section 7.4 takes an array as input and soils that array. At the beginning of Section 7.4 there is a simple pseudocode implementation for sorting a linked list using Mergesort. Implement both a linked list-based version of Mergesort and the array-based version of Mergesort, and compare and analyze their running times.

Solution

program

   

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Iterator;
public class Merge
{
        public static int[] merge(int [] list)
           {
               if (list.length <= 1)
               {
                return list;
              }
        int[] first = new int[list.length / 2];
        int[] second = new int[list.length - first.length];
        System.arraycopy(list, 0, first, 0, first.length);
        System.arraycopy(list, first.length, second, 0, second.length);
        merge(first);
        merge(second);
        mergesort(first, second, list);
        return list;
    }
        private static void mergesort(int[] first, int[] second, int [] result) {
        int iFirst = 0;
        int iSecond = 0;
        int j = 0;
        while (iFirst < first.length && iSecond < second.length)
           {
            if (first[iFirst] < second[iSecond])
              {
                result[j] = first[iFirst];
                iFirst++;
                } else
                  {
                result[j] = second[iSecond];
                iSecond++;
            }
            j++;
        }
        System.arraycopy(first, iFirst, result, j, first.length - iFirst);
        System.arraycopy(second, iSecond, result, j, second.length - iSecond);
    }
    public static void main(String args[]) throws Exception
    {
        String list=\"\";
        int i=0,n=0;
        Merge s= new Merge();
        ArrayList<Integer> arrlist=new ArrayList<Integer>();
        System.out.println(\" \");
        System.out.println(\" \");
        System.out.println(\"Please enter the list of elements,one element per line\");
        System.out.println(\" write \'STOP\' when list is completed \");
        BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));
        while(!(list=bf.readLine()).equalsIgnoreCase(\"stop\"))
        {
            int intelement=Integer.parseInt(list);
            arrlist.add(intelement);
        }
        int elementlist[] = new int[arrlist.size()];
        Iterator<Integer> iter = arrlist.iterator();
        for (int j=0;iter.hasNext();j++) {
            elementlist[j] = iter.next();
        }
        elementlist=merge(elementlist);
        System.out.println(\" \");
        System.out.println(\" \");
        System.out.println(\" \");
        System.out.println(\"Values after Merge Sort : \");
        for (int j=0;j<elementlist.length;j++)
         {
            System.out.println(elementlist[j]+\" \");
         }
    }
}