Cfrgtkky

I'm trying to write a generic Merge sort method in Java.

This is my source code:

import java.util.ArrayList;

import java.util.List;



/**

 * An implementation of MergeSort

 *

 * @param <T> the type of data held by the array.

 */

public class MergeSort<T extends Comparable<? super T>> implements ArraySort<T>

{

    /**

     * Sort the array using a MergeSort.

     *

     * (recursively breaks down the array into sub arrays until arrays of size 1 are reached.)

     * (then works backwards merging these arrays back into each other until a sorted array state is reached containing

     *  all the elements of the initial unsorted array, but now sorted).

     *

     * @param array the array to be sorted.

     * @return array (sorted)

     */

    @Override

    public T sort(T array)

    {

        //If the array being sorted is less than 2 elements, it is already sorted and cannot be split into two separate

        //     arrays, so return the initial array to prevent an exception.

        if(array.length < 2)

        {

            return array;

        }



        //Create two sub arrays from the initial array passed in.

        T temp1 = copy(array, 0, (array.length/2) - 1);

        T temp2 = copy(array, (array.length/2), array.length - 1);



        //Sort these two arrays.

        sort(temp1);

        sort(temp2);



        //Merge the two subarrays back into the initial array.

        merge(array, temp1, temp2);



        //return the now sorted array.

        return array;

    }



    /**

     * Create and return a new array, comprised of a sublist of a passed in array.

     *

     * @param list the array to create the subarray from.

     * @param from the lower bound within list to copy.

     * @param to the upper bound within list to copy.

     * @return a new list comprised of the elements from 'from' to 'to' in 'list'

     */

    private <T> T copy(T list, int from, int to)

    {

        List<T> copyL = new ArrayList<>();

        for(int i = 0; i < to - from + 1; i++)

        {

            copyL.add(list[from + i]);

        }

        return copyL.toArray(list);

    }



    /**

     * Merge two sorted arrays into one larger array, keeping the sorted.

     *

     * @param target the array to merge source1 and source2 into.

     * @param source1 a sorted array

     * @param source2 a second sorted array.

     */

    private void merge(T target, T source1, T source2)

    {

        //Variables to keep track of the smallest unused element in each source array.

        int source1Index = 0;

        int source2Index = 0;



        //targetIndex keeps track of the next index to place the next smallest element into.

        for(int targetIndex = 0; targetIndex < target.length; targetIndex++)

        {

            //Choose the smallest element from the two source arrays to place into the target(sorted) array

            if(source1[source1Index].compareTo(source2[source2Index]) < 0)

            {

                target[targetIndex] = source1[source1Index];

                source1Index++;

            }

            else

            {

                target[targetIndex] = source2[source2Index++];

                source2Index++;

            }

        }

    }

}

I have no idea why but I'm getting StackOverflow errors when I call line 38 and 42.

38 = T temp1 = copy(...) in the sort() method

42 = sort(temp1) in the sort() method.

This leads me to believe the error is somewhere in the copy function, but I don't know how to fix the problem or come to a solution.

Can somebody help me fix this implementation of a generic merge sort please?

StackTrace for sorting an array of 12 elements.

https://docs.google.com/document/d/1Ig5p7TZF_eX0Q_rroORnZUWnXtep7x-7cmDiSAZWlj8/edit?usp=sharing

Your array copying is wrong.

Use:

    private <T> T copy(T list, int from, int to) {

        return Arrays.copyOfRange(list, from, to);

    }

There are more bugs in your code (merge doesn't handle different length arrays) but this should fix your problem.

See List.toArray(T)

... If the list fits in the specified array, it is returned therein.

i.e. you are copying into the original array, not creating a new one, so your arrays never actually decrease in size.

Your conditional are not good enough, you get infinite sort call on your arrays.

At least you should include array of size equals to 2 :

if(array.length <= 2)

In addition, your copy method must be improved.

Anyway, copy/paste your full stack trace please.