Merge Sort Help

[Hollywood]

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

[Hollywood]

Bump. anyone?

[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.

[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");
    }
}

[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

[Hollywood]

Double Post