Over a million developers have joined DZone.

Merge Sort

·
// For some reason it's cutting the returned list in half. No idea why. After the last merge, it is the right size, but when it's returned to my other class, it's half the size...


import java.util.*;

public class Sorter 
{
    private static  > LinkedList merge(LinkedList
                                                list1, LinkedList list2)
   {
      LinkedList list = new LinkedList();
      while(!list1.isEmpty() && !list2.isEmpty())
      {
         if(list1.getFirst().compareTo(list2.getFirst()) < 0)
         {
            list.addLast(list1.removeFirst());
         }
         else 
         {
            list.addLast(list2.removeFirst());
         }   
      }
      list.addAll(list1);
      list.addAll(list2);
      return list;
   }
   
   public static  > LinkedList mergeSort(LinkedList list)
   {
      LinkedList leftList = new LinkedList();
      LinkedList rightList = new LinkedList();
      if(list.size() <= 1)
      {
         return list;
      }
      else
      {
         int middle = list.size() / 2;
         split(list, leftList, rightList, middle);
         leftList = mergeSort(leftList);
         rightList = mergeSort(rightList);
         list = merge(leftList, rightList);
         System.out.println("list size after merge: " + list.size());
         return list;
      }
   }
   
   private static  > void split(LinkedList list,
                               LinkedList leftList, LinkedList rightList,
                               int middle)
   {
      
      for(int i = 1; i <= middle; ++i)
      {
         leftList.addLast(list.removeFirst());
      }
      rightList.addAll(list);
   }
}

Topics:

The best of DZone straight to your inbox.

SEE AN EXAMPLE
Please provide a valid email address.

Thanks for subscribing!

Awesome! Check your inbox to verify your email so you can start receiving the latest in tech news and resources.
Subscribe

{{ parent.title || parent.header.title}}

{{ parent.tldr }}

{{ parent.urlSource.name }}