I need help writing a generic TimSort method for array lists. This is the code for the methods I have, but I cannot get it to work to due casting errors, maybe the whole merge method needs a rework. Please help. Below is the code for all the methods. At the very bottom is the tests it must "Pass".

/**

* A hybrid of Merge Sort and Insertion Sort.

* @param data The data in which the sub-array is located

* @param low Lower index of the sub-array.

* @param high Upper index of the sub-array.

*/

private static > void timSort(ArrayList data, int low, int high)

{

if ((high - low) >= 1)

{

int middle1 = (low + high) / 2;

int middle2 = middle1 + 1;

if (data.size() < TIM_SORT_LIMIT)

{

insertionSort(data);

}

else

{

timSort(data, low, middle1);

timSort(data, middle2, high);

}

merge(data, low, middle1, middle2, high);

}

}

/**

* Helper method for merge sort. Merges two sub-arrays into sorted order.

* @param data The data in which the sub-arrays are located

* @param left Lower index of first sub-array.

* @param middle1 Upper index of first sub-array.

* @param middle2 Lower index of second sub-array.

* @param right Upper index of second sub-array.

*/

private static > void merge(ArrayList data, int left, int middle1, int middle2, int right)

{

Integer leftIndex = left;

Integer rightIndex = middle2;

Integer combinedIndex = left;

int[] combined = new int[data.size()];

/*System.out.printf("merge: %s ", subarrayString(data, left, middle1));

System.out.printf(" %s ", subarrayString(data, middle2, right));*/

while (leftIndex <= middle1 && rightIndex <= right)

{

if (data.get(leftIndex).compareTo(data.get(rightIndex)) <= 0)

{

combined[combinedIndex++] = (Integer) data.get(leftIndex++);

}

else

{

combined[combinedIndex++] = (Integer) data.get(rightIndex++);

}

}

if (leftIndex == middle2)

{

while (rightIndex <= right)

{

combined[combinedIndex++] = (Integer) data.get(rightIndex++);

}

}

else

{

while (leftIndex <= middle1)

{

combined[combinedIndex++] = (Integer) data.get(leftIndex++);

}

}

for (int i = left; i <= right; i++)

{

Object mo=combined[i];

data.set(2, (T) mo);

//data[i] = combined[i];

}

//System.out.printf(" %s ", subarrayString(data, left, right));

}

/**

* Modified version of the Insertion Sort found in the slides and text.

* Only applies the Insertion Sort upon a sub-array specified by low and high.

* @param data The data in which the sub-array is located

* @param low Lower index of the sub-array.

* @param high Upper index of the sub-array.

*/

private static > void insertionSort(ArrayList data)

{

for (int next = 1; next < data.size(); next++)

{

T insert = data.get(next);

int moveItem = next;

while (moveItem > 0 && data.get(moveItem - 1).compareTo(insert) > 0)

{

data.set(moveItem,data.get(moveItem-1));

//data[moveItem] = data[moveItem - 1];

moveItem--;

}

data.set(moveItem,insert);

}

}

TESTS~~~~~~~~~~

import java.util.Random;

import java.util.ArrayList;

import mypackages.util.DataToolsAL;

public class Lab10ArrayListGenerics

{

/**

* Number of cases run for each test.

*/

private static final int NUM_TESTS = 5;

/**

* Exclusive limit for finding random numbers.

*/

private static final int RAND_LIMIT = 40;

/**

* Size of the arrays created for standard tests.

*/

private static final int ARRAY_TEST_SIZE = 20;

/**

* Random number generator for creating random data sets and search keys.

*/

private static Random rand = new Random();

/**

* Main method for DataTools testing.

* @param args Not used.

*/

public static void main(String[] args)

{

//Test your tim sort implementation

System.out.println(" TESTING TIM SORT");

for (int i = 0; i < NUM_TESTS; i++)

{

System.out.printf("***Tim Sort Test %d*** ", i + 1);

System.out.println("--TESTING WITH INTEGERS--");

testTimSortInteger();

System.out.println("--TESTING WITH DOUBLES--");

testTimSortDouble();

}

}

/**

* A single test of your tim sort with Integers.

*/

private static void testTimSortInteger()

{

//Create and populate data set

ArrayList data = new ArrayList();

populateDataInteger(data, 1);

//Output original state of the data

System.out.println("ORIGINALLY ORDERED ");

outputData(data);

//Sort and output the ordered data set

DataToolsAL.timSort(data);

System.out.println("SORTED ORDER ");

outputData(data);

//Determine if data is in fact sorted

System.out.printf("TEST %s ", checkOrder(data) ? "PASSED" : "FAILED");

}

/**

* A single test of your tim sort with Doubles.

*/

private static void testTimSortDouble()

{

//Create and populate data set

ArrayList data = new ArrayList();

populateDataDouble(data, 1);

//Output original state of the data

System.out.println("ORIGINALLY ORDERED ");

outputData(data);

//Sort and output the ordered data set

DataToolsAL.timSort(data);

System.out.println("SORTED ORDER ");

outputData(data);

//Determine if data is in fact sorted

System.out.printf("TEST %s ", checkOrder(data) ? "PASSED" : "FAILED");

}

/**

* Given a set of data, determines if the elements are in order.

* @param data Data set to check the order of.

* @param Generic type found in the passed ArrayList. Must be Comparable in order

* to check if order is correct.

* @return Whether or not the data set is in order.

*/

private static > boolean checkOrder(ArrayList data)

{

//Go through the data

for (int i = 0; i < data.size() - 1; i++)

{

//If an unordered pair is found return false...

if (data.get(i).compareTo(data.get(i + 1)) > 0)

{

return false;

}

}

//Otherwise it's all good!

return true;

}

/**

* Randomly populates a given array.

* @param data Array to be randomly populated.

* @param randMultiplier Multiplier to be used with RAND_LIMIT.

*/

private static void populateDataDouble(ArrayList data, int randMultiplier)

{

//Go through each element in array

for (int i = 0; i < ARRAY_TEST_SIZE; i++)

{

//Randomly generate value for current element

data.add((double) rand.nextInt(RAND_LIMIT) * randMultiplier);

}

}

/**

* Randomly populates a given array.

* @param data Array to be randomly populated.

* @param randMultiplier Multiplier to be used with RAND_LIMIT.

*/

private static void populateDataInteger(ArrayList data, int randMultiplier)

{

//Go through each element in array

for (int i = 0; i < ARRAY_TEST_SIZE; i++)

{

//Randomly generate value for current element

data.add(rand.nextInt(RAND_LIMIT) * randMultiplier);

}

}

/**

* Outputs all elements in an ArrayList, showing indices below.

* @param data Array to be output.

* @param Generic type found in the passed ArrayList.

*/

private static void outputData(ArrayList data)

{

//Output the data

System.out.printf("%-7s", "DATA:");

for (int i = 0; i < data.size(); i++)

{

System.out.printf("%4s ", data.get(i));

}

//Output the indices

System.out.printf(" %-7s", "INDEX:");

for (int i = 0; i < data.size(); i++)

{

System.out.printf("%4d ", i);

}

//End with a new line

System.out.println();

}

}