Merge Sort Java Program

Java Program to implement Merge sort algorithm using Linked list as a data structure

import java .io.*;

import java.util.*;

class Sorter {

    LinkedList <Integer> merge(LinkedList <Integer>list1, LinkedList <Integer>list2)   {

        LinkedList <Integer> list = new LinkedList <Integer>();

        while((!list1.isEmpty())&&!list2.isEmpty())   {

           if(list1.getFirst().compareTo(list2.getFirst())<0)

               list.add(list1.removeFirst());

           else    list.add(list2.removeFirst());

       }

       list.addAll(list1);       list.addAll(list2);

       return list;

   }

   LinkedList <Integer> mergesort(LinkedList <Integer>list)   {

                LinkedList <Integer> leftlist = new LinkedList <Integer>();

                LinkedList <Integer> rightlist = new LinkedList <Integer>();

                if(list.size()<=1)

                    return list;

                int middle=list.size()/2;

                split(list,leftlist,rightlist,middle);

                leftlist=mergesort(leftlist);

                rightlist=mergesort(rightlist);

                list=merge(leftlist,rightlist);

                return list;

  }

  void split(LinkedList<Integer> list, LinkedList<Integer> leftlist, LinkedList<Integer> rightlist, int  mid) 

  {

        for(int i=1;i<=mid;i++)

            leftlist.addLast(list.removeFirst());

        rightlist.addAll(list);

  }

}

 

public class Mergesort {

    public static void main(String args[]) throws IOException   {

                Sorter s=new Sorter();

                LinkedList <Integer> list=new LinkedList <Integer> ();

                DataInputStream in=new DataInputStream(System.in);

                System.out.print("Enter how many numbers");

                int n=Integer.parseInt(in.readLine());

                  System.out.print("Enter any "+n+" integer elements");

                for(int x=1;x<=n;x++)

                     list.add(Integer.parseInt(in.readLine()));

                System.out.println("Berfore Sorting "+list);

                System.out.println("After Sorting "+s.mergesort(list));

    }   

}

 

 OUTPUT:

Enter how many numbers 6

Enter any 6 integer elements

8  6 4 2 1 3

Berfore Sorting [8, 6, 4, 2, 1, 3]

After Sorting [1, 2, 3, 4, 6, 8]