1. Member
Join Date
Jan 2008
Posts
8
Rep Power
0

## 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.
Java 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```

2. Member
Join Date
Jan 2008
Posts
8
Rep Power
0
Bump. anyone?

3. 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:

Java 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.
Java Code:
`   ? extends E`
The specified type must be a subclass of E

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

Java Code:
`   ?`
All types

Hope that information helps you, and anyone interested in generic programming.
Last edited by gibsonrocker800; 01-29-2008 at 07:59 AM.

4. Java 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++)
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");
}
}```

5. Member
Join Date
Jan 2008
Posts
8
Rep Power
0
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
Java 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```
Last edited by Hollywood; 01-30-2008 at 07:23 AM.

6. Member
Join Date
Jan 2008
Posts
8
Rep Power
0
Double Post
Last edited by Hollywood; 01-30-2008 at 07:23 AM.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•