A generic MergeSort implementation in java

Question

I have written a MergeSort implementation that should sort an array of any data type.

Am facing 2 issues here.

1. Since Generic types cannot be defined as an array as the compiler errors out saying that 'cannot create a generic array of T', I have followed a kludge suggested in one of the threads in StackOverflow to use

   T[] right = (T[]) Array.newInstance(clazz, rightSize);

so that with the type info supplied during runtime, we still can instantiate an array and cast it back to T[] though it is still vulnerable to ClassCastException irrespective of whether we handle it or not.

Is there any other efficient and ideal way of achieving this?

2. Now the below merge sort algorithm works based on Generics, I cannot supply an array of primitive types like int[] in the place of T[].

So should i need to create the MergeSort class one version for each of primitive typed array that i wanted to sort?

3. In general, can this algorithm be improved further?

Any help would be greatly appreciated. Thanks.

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Comparator;

public class MergeSort {

    public <T> void sort(T[] values, Class<T> clazz, Comparator<T> comparator) {
        if (values == null) {
            throw new IllegalArgumentException("values is null.");
        }

        // recursion exit criteria.
        if (values.length < 2) {
            return;
        }

        // segregate the values array into 2 halves.
        int median = values.length / 2;
        int leftSize = median;
        int rightSize = values.length - median;

        // construct the left array.
        T[] left = (T[]) Array.newInstance(clazz, leftSize);
        for (int l = 0; l < leftSize; ++l) {
            left[l] = values[l];
        }

        // construct the right array.
        T[] right = (T[]) Array.newInstance(clazz, rightSize);
        for (int r = 0; r < rightSize; ++r) {
            right[r] = values[leftSize + r];
        }

        // recursively do merge sort on either side of the array.
        sort(left, clazz, comparator);
        sort(right, clazz, comparator);

        // merges the left and right and keeps the intermediate
        // values array sorted as it works it's way up.
        _merge(values, left, right, comparator);

    }

    private <T> void _merge(T[] values, T[] left, T[] right, Comparator<T> comparator) {
        int leftIndex = 0;
        int rightIndex = 0;
        int sortedIndex = 0;

        while (leftIndex < left.length && rightIndex < right.length) {
            int comparison = comparator.compare(left[leftIndex], right[rightIndex]);
            if (comparison <= 0) {
                values[sortedIndex] = left[leftIndex];
                leftIndex++;
            } else {
                values[sortedIndex] = right[rightIndex];
                rightIndex++;
            }
            sortedIndex++;
        }

        // Handle the left over elements if any in the left side
        // and places them in the sorted array.
        while (leftIndex < left.length) {
            values[sortedIndex] = left[leftIndex];
            leftIndex++;
            sortedIndex++;
        }

        // Handle the left over elements if any in the right side.
        // and places them in the sorted array.
        while (rightIndex < right.length) {
            values[sortedIndex] = right[rightIndex];
            rightIndex++;
            sortedIndex++;
        }
    }

    public static void main(String[] args) {
        Integer[] values = new Integer[] { 5, 0, 10, 4, 1, 8, 3, 9, 6, 2, 7 };

        new MergeSort().sort(values, Integer.class, new Comparator<Integer>() {

            @Override
            public int compare(Integer o1, Integer o2) {
                return o1.compareTo(o2);
            }
        });

        System.out.println(Arrays.toString(values));
    }
}

Answer 1

To your first question: You can use

T[] newArray = (T[]) new Object[newSize];

You can guarantee that this cast will always succeed and that the new array will always only hold Ts. Thus, the cast is rectified. To suppress the unchecked cast-warning, mark the method with @SuppressWarnings("unchecked"). A similar approach is by the way used for OpenJDK's implementation of ArrayList.

---

To your second question: For optimal performance, yes. You should provide one implementation per primitive type. Covariance and autoboxing are not sufficient to convert an int[] into an Integer[].

---

To your third question: Instead of creating new arrays for the left and right part, you could acutally re-use the old array, and just pass left and right as parameters down your recursive calls. See this github link for an implementation.

---

A remark on your code: In Java, a method name should always start with a lowercase letter. While I know that it is common in C++ to start a private methode with an _, this is not the case in Java.

---

Some general remarks to your question:

• You should limit yourself to one question per post.
• If your code is functional and you want feedback on your code, Code Review might be better suited for that.