Merge sort algorithm error

Question

Hey all I have been working on a merge sorter app with java in Eclipse. For some reason I can't figure it out and it is making me mad...

This is the main file I am working with

public class MergeSorter {

    public Integer[] sort(Integer[] array) {
        return mergesort(array);
    }


    private Integer[] mergesort(Integer[] array) {
      if(array.length > 1) {
          Integer[] left = new Integer[array.length /2];
          Integer[] right = new Integer[array.length - left.length];

          mergesort(left);
          mergesort(right);

          merge(left, right);
        }
        return array;
    }


    public Integer[] merge(Integer[] left, Integer[] right) {
        int leftI = 0;
        int rightI = 0;
        int newI = 0;
        Integer[] newArr = new Integer[left.length + right.length];

        while (leftI < left.length && rightI < right.length) {
            if (left[leftI] < right[rightI]) {
                newArr[newI] = left[leftI];
                leftI++;
            } else {
                newArr[newI] = right[rightI];
                rightI++;
            }
            newI++;
        }

        // Either the left or the right may still have elements
        for (int i = leftI; i < left.length; i++) { // left
            newArr[newI] = left[i];
            newI++;
        }
        for (int i = rightI; i < right.length; i++) { // right
            newArr[newI] = right[i];
            newI++;
        }
        return newArr;
    }


    public void printCollection(Integer[] items) {
        for (int i = 0; i < items.length; i++) {
            System.out.print(items[i] + " ");
        }
        System.out.println();
    }
}

There is also a driver file that has everything done it it to run this code. I was told I need to genercize the merger sorter class to using arrayLists rather than arrays, but I am lost on how to do so. I am thinking this is where i need to use the List ? but not sure on it, any help is appreciated

Answer 1

There two major wholes in your logic. First, your mergesort returns it's input no matter what. Second, your merged array is never stored.

private Integer[] mergesort(Integer[] array) {
  if(array.length > 1) {
      Integer[] left = new Integer[array.length /2];
      Integer[] right = new Integer[array.length - left.length];

      mergesort(left); //problem 1.5: more on this later...
      mergesort(right);

      merge(left, right); //problem 2: stored array is returned but not stored
    }
    return array; //problem 1: returns array unchanged
}

Solving problem 2 is simple. We just need to assign the output to a field like so:

Integer[] result = merge(left,right);

or

array = merge(left,right);

Using either or these, result or array will not retain the work done in merge(). The strategy you choose will depend whether or not you want to modify your input.

The relationship may actually be counter intuitive, but if you want your input to remain unchanged you can use the second line and now also problem 1 is solved because we've changed array. (The input is unchanged because Java is pass-by-value meaning array is a new field with the same array as your input, not the same field containing that array, thus assignment makes puts a separate array in the field array without touching the original). Unfortunately this solution leaves us with problem 1.5, because we're not changing left and right by calling mergesort(), in which case we need to store as we did the results of merge().

If you want to mergesort() to change the input array (which is not an unreasonable idea) then we need to create the separate Integer[] results given above and copy it's values to the array held int array. This also adverts problem 1.5 but may change the intent of you method.

EDIT: There is a third problem I neglected to mention. In mergesort() you've created left and right but they are never filled. You should copy the values from array into your left or right halves. Something like:

for(int i=0; i<left.length; i++) left[i] = array[i];
for(int i=0; i<right.length; i++) right[i] = array[left.length+i];

---

Now to answer you're second question, it should not be hard to do every thing you've done with an ArrayList<Integer>. The documentation list all the methods and you can treat an ArrayList as array often (execpt instead of array[i] or array[i]=value you have to use methods array.get(i) and array.set(i,value)). However you can simplify things by using methods like array.add(value) which puts a value at the end of the list so that you don't have to keep up with where the end actually is.

Hopefully this helps you understand exactly where your problems lie and resolve them so your brain can itch over all the other wonderful details programming provides