# Merge Sort Help

• 01-25-2008, 05:14 PM
Hollywood
Merge Sort Help
Hello everyone, I am new to the Forum.
I have a homework problem implementing the merge sort using generic list not w/ an array. I didn't see anything online about using it w/ list. I was wondering if you could give me a hand w/ my code. I understand everything untill the actual merging of the list, and just can't seem to get the algorithm. Keep in mind I am sorting the list as is and not copying it into sub-lists as to keep efficiency. Thanks for any of your help.
Code:

```package sort; import utilities.containers.*; /**  * This class subdivides a list of elements into a subsequences of elements,  * then merges the single elements in order to form a single ordered list.  */ public class MergeSort <E>{     /**   * MergeSort Starting algorithm.   *      Require: a non-empty list of elements to sort.   *      Ensure: returns the input list in increasing order.   *   */     public void mergesort(List <E> toSort){         if (toSort.size()<=1){       /*Do Nothing*/     }     else{             int low = 0;       int high = toSort.size()-1;             sort(toSort,low,high);             }       }     /**   * Private sort method used to break down input list into single list elements.   *   */     private void sort(List <E> toSort,int low,int high){         if(low==high){       /*Do Nothing*/     }     else{       int middle = (high+low)/2;             sort(toSort,low,middle);       sort(toSort,middle,high);       merge(toSort,low, middle, high);           }   }     /**   * Private merge method used to merge and order two generic lists.   */     private void merge(List<E> toSort,int low, int middle, int high){       /**   *This is the area I don't get.   */       }     /**   * Swaps two generic elements of a list.   */     private void swap(List<E> toSort,int left, int right){       E temp = toSort.get(left);     toSort.set(left,toSort.get(right));     toSort.set(right,temp);       }   }//end of class MergeSort```
• 01-26-2008, 04:59 PM
Hollywood
Bump. anyone?
• 01-29-2008, 07:56 AM
gibsonrocker800
I'm not too good at generic programming, but i believe that E will have to be a Comparable because how else will the MergeSort know how to sort these elements. So, you have to write something like this for the class declaration:

Code:

``` public class MergeSort<E extends Comparable>```
Saying E extends Comparable means E extends or implements the following class or interface, so in this case, we're saying E implements Comparable.
You may need to incorporate this information somewhere in your class, because i don't understand how else you can sort Objects if they can't be compared.

There are many other things you can do with these limitations. They are called wildcards.
Code:

`  ? extends E`
The specified type must be a subclass of E

Code:

`  ? super E`
The specified type must be a superclass of E

Code:

`  ?`
All types

Hope that information helps you, and anyone interested in generic programming.
• 01-29-2008, 09:19 AM
hardwired
Code:

```import java.util.*; public class MergeSortRx {     public <T extends Comparable<? super T>> void mergesort(List<T> toSort) {         if (toSort.size()<=1){             /*Do Nothing*/         }         else{             int low = 0;             int high = toSort.size()-1;             print(toSort, "original collection");             sort(toSort, low, high);         }     }     private <T extends Comparable<? super T>> void sort(List<T> toSort,                                                         int low, int high) {         if(low == high){             /*Do Nothing*/             return;         }         else{             int middle = (high+low)/2;             sort(toSort, low, middle);             sort(toSort, middle+1, high);             merge(toSort, low, middle, high);         }     }     private <T extends Comparable<? super T>> void merge(List<T> toSort,                               int low, int middle, int high) {         int loCount = low;         int midCount = middle;         int hiCount = middle+1;         while(loCount <= midCount && hiCount <= high) {             T lo = toSort.get(loCount);             T hi = toSort.get(hiCount);             int compare = lo.compareTo(hi);             if(compare < 0) {    // lo < hi                 loCount++;             } else {            // lo >= hi                 T temp = hi;                 for(int j = hiCount-1; j >= loCount; j--)                     toSort.set(j+1, toSort.get(j));                 toSort.set(loCount, temp);                 loCount++;                 midCount++;                 hiCount++;             }         }     }     private <T> void print(List<T> list, String title) {         System.out.println(title);         for(int j = 0; j < list.size(); j++) {             System.out.print(list.get(j));             if(j < list.size()-1)                 System.out.print(", ");         }         System.out.println();     }     public static void main(String[] args) {         MergeSortRx ms = new MergeSortRx();         int[] ints = { 5, 7, 9, 3, 16, 12, 4 };         List<Integer> list = new ArrayList<Integer>();         for(int j = 0; j < ints.length; j++)             list.add(Integer.valueOf(ints[j]));         ms.mergesort(list);         ms.print(list, "after sorting");         System.out.println("--------------");         String[] s = "bdoaplvjertmxn".split("(?<=[\\w])");         List<String> sList = Arrays.asList(s);         ms.mergesort(sList);         ms.print(sList, "after sorting");     } }```
• 01-30-2008, 04:17 AM
Hollywood
Hardwired, I just need to find a way to use your merge in my merge.

Ok I am sorry I forgot to implement an order I am not using Comparable.
Here is my new code. I have some of the merge algorithm but am a little stuck.
I have tested the split method and it is splitting fine it is when I merge, and I have more than two elements of each half when some aren't fully comparing w/ the others.

I am inputing this list of Integers "8,4,1,6,4,3,2,6"
my output so far looks like this "1,2,3,6,6,4,4,8"
4 is not after 6
Code:

```package sort; import utilities.containers.*; /**  * This class subdivides a list of elements into a subsequences of elements,  * then merges the single elements in order to form a single ordered list.  */ public class ListUtilities {     /**   * MergeSort Starting algorithm.   *      Require: a non-empty list of elements to sort.   *      Ensure: returns the input list in increasing order.   */     public static <E> List <E> mergesort(Order<E> order,List <E> toSort){         List<E> result = toSort.copy();         if (toSort.size()<=1){       /*Do Nothing*/     }     else{                   int low = 0;       int high = result.size()-1;       split(order,result,low,high);     }     return result;       }     /**   * Private split method used to break down input list into single list elements.   *   */     private static <E> void split(Order<E> order,List <E> toSort,int low,int high){         if(low==high){       /*Do Nothing*/       //return split;     }     else{             int middle = (high+low)/2;             split(order,toSort,low,middle);       split(order,toSort,middle+1,high);       merge(order,toSort,low, middle, high);           }   }     /**   * Private merge method used to merge and order two generic lists.   * As elements are merged they are sorted according to order.   */     private static <E> void merge(Order<E> order,List<E> toSort,int low, int middle, int high){     int i = middle;     int j = middle+1;         while((low<=i)&&(j<=high)){       if(order.inOrder(toSort.get(low),toSort.get(j))){         low++;       }       else{         swap(toSort,low,j);         j++;       }     }   }     /**   * Swaps two generic elements of a list.   */     private static <E> void swap(List<E> toSort,int left, int right){       E temp = toSort.get(left);     toSort.set(left,toSort.get(right));     toSort.set(right,temp);       }   }//end of class MergeSort```
• 01-30-2008, 04:26 AM
Hollywood
Double Post