Need help streamlining my Merge Sort implementation

Question

I am building a class of sortable ArrayLists which extends ArrayList. The goal is to be able to call a sort method on a SortDoubleArray, and have that array be sorted via the method described. I got Quicksort, Insertion Sort, Bubble Sort, and Selection Sort all working as I want. I am having some difficulty with Merge Sort, however.

The sort works, but due to the way the recursion involved is working, I am forced reset the contents of the list to be the method applied to itself.

First, here is the tester class. It shows how the other sorts are being implemented. If I did a poor job explaining my issue, hopefully you will see the difference in how the mergeSort() method must be used.

public class SortTester
{
    /**
     * @param args
     */
    public static void main(String[] args)
    {
        SortDoubleArray list = new SortDoubleArray();

        // Code to fill an array with random values.

        //list.quickSort();
        //list.insertionSort();
        //list.selectionSort();
        //list.bubbleSort();
        list = list.mergeSort();

        // Code to print the sorted array.
    }
}

Next, here is the SortDoubleArray class. All of the other sorts but insertionSort (to serve as an example of one working the way I want) have been removed for brevity.

public class SortDoubleArray extends ArrayList<Double>
{ // Start of class.
    private static final long serialVersionUID = 1271821028912510404L;

    /**
     * Progresses through the elements one at a time inserting them in their proper place
     * via swaps.
     */
    public void insertionSort()
    { // Start of insertionSort.
        int current = 1;

        while (current < size())
        {
            int i = current;
            boolean placeFound = false;

            while(i > 0 && !placeFound)
            {
                if (get(i) < get(i - 1))
                {
                    double temp = get(i);
                    set(i, get(i - 1));
                    set(i - 1, temp);
                    i -= 1;
                }
                else
                {
                    placeFound = true;
                }
            }
            current += 1;
        }
    } // End of insertionSort.

    /**
     * Triggers the recursive mSort method.
     * @return 
     */
    public SortDoubleArray mergeSort()
    { // start of mergeSort.
        return mSort(this);
    } // End of mergeSort.

    /**
     * Separates the values each into their own array.
     */
    private SortDoubleArray mSort(SortDoubleArray list)
    { // Start of mSort.
        if (list.size() <= 1)
        {
            return list;
        }

        SortDoubleArray left = new SortDoubleArray();
        SortDoubleArray right = new SortDoubleArray();

        int middle = list.size() / 2;

        for (int i = 0; i < middle; i += 1)
        {
            left.add(list.get(i));
        }

        for (int j = middle; j < list.size(); j += 1)
        {
            right.add(list.get(j));
        }

        left = mSort(left);
        right = mSort(right);

        return merge(left, right);
    } // End of mSort.

     /**
     * Merges the separated values back together in order.
     */
    private SortDoubleArray merge(SortDoubleArray left, SortDoubleArray right)
    { // Start of merge.
        SortDoubleArray result = new SortDoubleArray();

        while (left.size() > 0 || right.size() > 0)
        {
            if (left.size() > 0 && right.size() > 0)
            {
                if (left.get(0) <= right.get(0))
                {
                    result.add(left.get(0));
                    left.remove(0);
                }
                else
                {
                    result.add(right.get(0));
                    right.remove(0);
                }
            }
            else if (left.size() > 0)
            {
                result.add(left.get(0));
                left.remove(0);
            }
            else if (right.size() > 0)
            {
                result.add(right.get(0));
                right.remove(0);
            }
        }

        return result;
    } // End of merge.
} // End of class.

Please give me some ideas on how I can alter the mergeSort() / mSort() functions within the SortDoubleArray class to have the same implementation as the rest of the sorts.

Thank you!

Answer 1

Given that mSort and merge methods are correct, how about this ?

public void mergeSort()
{ // start of mergeSort.
    SortDoubleArray result = mSort(this);
    clear();
    addAll(result);
} // End of mergeSort.

The relevant line in your test would then be:

    list.mergeSort();

Good luck!