Sorting An Array of Generic Type

Question

I am trying to implement Merge Sort algorithm on an array of genetic type. The problem is that the result is incorrect since some elements were set to 0. I suspect that the problem came from the casting I did through out the program, but I do not know exactly why.

As you can see in sortUsingMerge(), I casted an array of Object to generic. Also in the IF statement below, I casted the Object element in the array to int to be able to compare 2 elements. My intention is that the sorting algorithm should work for any array of any type, but I just do not want to write the Comparator for each type for now.

Input array: 5 1 -2 3 7 8 0
Output: -2 0 1 1 3 7 0

Look like number 5 and 8 were somehow converted to different numbers during the sorting. Can someone show me why? Thanks!

Source code:

public void sortUsingMerge(){
    Object[] array = (E[]) new Object[size];
    Object[] helper = (E[]) new Object[size];

    mergeSort(array,helper,0,size-1);

}
 public void mergeSort(Object[] array, Object[] helper, int low, int high){

       if (low<high){ 

            int mid = (low + high)/2;

            mergeSort(array,helper,low,mid); //sort left half
            mergeSort(array,helper,mid+1,high);//sort right half
            merge(array,helper,low,mid,high);

        }
}
public void merge(Object[] array, Object[] helper, int low, int mid, int high){

    for (int i=low; i<=high; i++){// copy both parts into helper array
        helper[i] = array[i];
    }

    int helperLeft = low;
    int helperRight = mid + 1;
    int current = low;

    while (helperLeft <= mid && helperRight <=high){

        if ((int)helper[helperLeft] <= (int)helper[helperRight]){
            array[current] = helper[helperLeft];
            helperLeft++;
        }
        else{
            array[current] = helper[helperRight];
            helperRight++;
        }

        current++;
    }


    int remain = mid - helperLeft;
    for (int i=0; i<remain; i++){
        array[current+i] = helper[helperLeft + i];
    }


}

It would appear you're losing numbers because you didn't make a "deep" copy for your left and right arrays.. you merely modify in place. Do as mitch suggested and debug .. — Erik
– Erik, Commented Nov 23, 2013 at 7:13
if you are casting your array element to int in your logic, why use generics? — Adrian Shum
– Adrian Shum, Commented Nov 23, 2013 at 7:50
My intention was to make the sorting work for any type of element. However I wanted to quickly check to see if it worked with integers first. Without the cast, I cannot compare an E to another E. — Charlie Victor
– Charlie Victor, Commented Nov 23, 2013 at 16:48

Vipul Paralikar · Accepted Answer · 2013-11-23 10:11:35Z

4

inside merge replace

    for (int i=0; i<remain; i++){
     array[current+i] = helper[helperLeft + i];
    }

with

    while (helperLeft <= mid) {
        array[current] = helper[helperLeft];
        current++;
        helperLeft++;
    }

edited Nov 23, 2013 at 10:11

answered Nov 23, 2013 at 7:42

Vipul Paralikar

1,57810 silver badges22 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

user684934 Over a year ago

Link-only answers are discouraged here, for multiple reasons. Please put an actual, concise answer to the specific problem here.

Vipul Paralikar Over a year ago

@bdares concise answer has been placed.

Charlie Victor Over a year ago

It fixed the problem. I did not expect problem came from the algorithm itself :) Thanks!

Paul Draper · Accepted Answer · 2013-11-23 16:46:35Z

1

Casting would never give you that kind of error. You have bug at the end of your merge.

    int remain = mid - helperLeft;
    for (int i=0; i <= remain; i++) {                 //changed < to <=
        array[current+i] = helper[helperLeft + i];
    }

edited Nov 23, 2013 at 16:46

answered Nov 23, 2013 at 7:13

Paul Draper

84.2k53 gold badges216 silver badges303 bronze badges

1 Comment

Charlie Victor Over a year ago

I believe the 2nd for loop is not necessary since the biggest elements are always moved to right end of the original array.

Collectives™ on Stack Overflow

Sorting An Array of Generic Type

2 Answers 2

3 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related