DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Snippets has posted 5883 posts at DZone. View Full User Profile

Merge Sort

05.17.2009
| 4950 views |
  • submit to reddit
        // 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 <T extends Comparable<T> > LinkedList<T> merge(LinkedList<T>
                                                list1, LinkedList<T> list2)
   {
      LinkedList<T> list = new LinkedList<T>();
      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 <T extends Comparable<T> > LinkedList<T> mergeSort(LinkedList<T> list)
   {
      LinkedList<T> leftList = new LinkedList<T>();
      LinkedList<T> rightList = new LinkedList<T>();
      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 <T extends Comparable<T> > void split(LinkedList<T> list,
                               LinkedList<T> leftList, LinkedList<T> rightList,
                               int middle)
   {
      
      for(int i = 1; i <= middle; ++i)
      {
         leftList.addLast(list.removeFirst());
      }
      rightList.addAll(list);
   }
}