Over a million developers have joined DZone.
{{announcement.body}}
{{announcement.title}}

Merge Sort

DZone's Guide to

Merge Sort

·
Free Resource
// 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:

Opinions expressed by DZone contributors are their own.

THE DZONE NEWSLETTER

Dev Resources & Solutions Straight to Your Inbox

Thanks for subscribing!

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

X

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

{{ parent.tldr }}

{{ parent.urlSource.name }}