javaでTimSortをしたい

Question

javaでTimSortアルゴリズムのプログラムを書いています。
insertionSortメソッドとmergeSortメソッドが正しく動くことは確認できていて、
timSortメソッド内で再帰プログラムを書きたいのですが、どのようなコードを書けば良いかわかりません。

insertionSort、またはmergeSortメソッドに
配列を入れると、正しくソートはしてくれますが、要素が多いと動きがとてつもなく遅くなります。
そこで、その２つのメソッドを利用したTimSortアルゴリズムを書きたいのですが、どのタイミングで何をどのメソッドに入れれば良いかが全く分かりません。

配列の長さが100だとすると、それを、50、25、12、という風に長さが10以下になるまではmergeSortを、
それ以降はinsertionSortを利用したいです。

public class Sorting
{
	///////////////////////////////////////////////
	//  STEP 1 -- Make sorting methods generic
	///////////////////////////////////////////////
	
	/**
	 * Re-orders the contents given array using the insertion sort algorithm.
	 * 
	 * @param <E> Generic to store the different values.
	 * @param data The array to be sorted.
	 */
	public static <E extends Comparable<E>> void insertionSort(E[] data) 
	{
		E insert; // temporary variable to hold element to insert
		
		// loop over data.length - 1 elements
		for (int next = 0; next < data.length; next++) 
		{ 
			insert = data[ next ]; // store value in current element
			int moveItem = next; // initialize location to place element
		   
			while (moveItem > 0 && data[ moveItem - 1 ].compareTo(insert) > 0) 
			{           
				data[ moveItem ] = data[ moveItem - 1 ]; 
				moveItem--;
			} 
		   
			data[ moveItem ] = insert; // place inserted element
		}
	}
	
	/**
	 * Sorts passed data using Merge Sort by modifying the input array. 
	 * 
	 * @param <E> Generic to store the different values.
	 * @param data The data to be sorted.
	 */
	public static <E extends Comparable<E>> void mergeSort(E[] data)
	{
		mergeSortHelper(data, 0, data.length - 1);
	}
	
	/**
	 * Recursive helper method for mergeSort.
	 * 
	 * @param <E> Generic to store the different values.
	 * @param data The data in which the sub-array is located
	 * @param left Lower index of the sub-array.
	 * @param right Upper index of the sub-array.
	 */
	private static <E extends Comparable<E>> void mergeSortHelper(E[] data, int left, int right)
	{
		//General Case: The sublist has at least one item in it.
		if ((right - left) >= 1)	
		{
			int middle1 = (left + right) / 2;
			int middle2 = middle1 + 1;
			
			mergeSortHelper(data, left, middle1);
			mergeSortHelper(data, middle2, right);

			merge(data, left, middle1, middle2, right);
		}
	}
	
	/**
	 * Helper method for merge sort. Merges two sub-arrays into sorted order.
	 *
	 * @param <E> Generic to store the different values.
	 * @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.
	 */
	@SuppressWarnings("unchecked")
	private static <E extends Comparable<E>> void merge(E[] data, int left, int middle1, int middle2, int right)
	{
		int leftIndex = left;					// Local variables for tracking left and right
		int rightIndex = middle2;				// while merging.
		
		Object[] combined = new Object[data.length]; 
		
		int combinedIndex = left;		       
		while (leftIndex <= middle1 && rightIndex <= right)
		{
			// Is the first item of the left subarray smaller?
			if (data[leftIndex].compareTo(data[rightIndex]) <= 0)
			{
				combined[combinedIndex++] = data[leftIndex++];
			}
			// Or is the first item in the right one smaller?
			else 
			{
				combined[combinedIndex++] = (E) (data[rightIndex++]);
			}
		}

		if (leftIndex == middle2)
		{
			while (rightIndex <= right)
			{
				combined[combinedIndex++] = data[rightIndex++];
			}
		}
		else
		{
			while (leftIndex <= middle1)
			{
				combined[combinedIndex++] = data[leftIndex++];
			}
		}
		for (int i = left; i <= right; i++)
		{
			data[i] = (E) (combined[i]);
		}		
	}

	
	///////////////////////////////////////////////////////
	// STEP 2  - Refactor Insertion Sort
	//
	//Write the helper method described below and then 
	// simplify insertionSort to eliminate duplicate code
	///////////////////////////////////////////////////////
	
	/**
	 * insertionSortRange is a generic method that allows for
	 * sorting a sub-range of Comparable array values using the 
	 * insertion sort algorithm.  
	 * 
	 * Ranges are specified with the parameters left and right, 
	 * which are inclusive.
	 * 
	 * @param <E> Generic to store the different values.
	 * @param data  The array of data to sort
	 * @param left  The index of the left-most position to sort
	 * @param right The index of the right most position to sort
	 */
	//Write the method header and body for insertionSortRange here
	public static <E extends Comparable<E>> void insertionSortRange(E[] data, int left, int right) 
	{
		E insert; // temporary variable to hold element to insert
		int leftPosi = left - 1;
		int rightPosi = right + 1;
		// loop over data.length - 1 elements
		for (int next = leftPosi; next < rightPosi; next++) 
		{ 
			insert = data[ next ]; // store value in current element
			int moveItem = next; // initialize location to place element
		   
			// shift items in the sorted part of the array to make room for next element
			// making sure we don't step off the front of the array
			while (moveItem > leftPosi && data[ moveItem - 1 ].compareTo(insert) > 0) 
			{           
				data[ moveItem ] = data[ moveItem - 1 ]; // shift element right one slot
				moveItem--;
			} 
		   
			data[ moveItem ] = insert; // place inserted element
		}
	}

	
	//////////////////////////////////////////////////////
	// STEP 3 - Complete TimSort
	//////////////////////////////////////////////////////
	
	/**
	 * timSort is a generic sorting method that sorts an array of Comparable
	 * data using the TimSort algorithm.  Make sure this method is public so
	 * that we can test it.
	 * 
	 * @param <E> Generic to store the different values.
	 * @param data  The array of data to be sorted
	 */
	//Write the method header for timSort here.  Just uncomment the body, do not edit it.
	
	public static <E extends Comparable<E>> void timSort(E[] data) 
	{
		timSortHelper(data, 0, data.length - 1);
		
	}
	
	
	/**
	 * timSortHelper is a generic sorting method that sorts a sub-array array of Comparable
	 * data using the TimSort algorithm.  This method should be public for testing purposes
	 * but would normally be private.
	 * 
	 * Ranges are specified with the parameters left and right, 
	 * which are inclusive.
	 * 
	 * @param <E> Generic to store the different values.
	 * @param data  The array of data to sort
	 * @param left  The index of the left-most position to sort
	 * @param right The index of the right most position to sort
	 */
	public static <E extends Comparable<E>> void timSortHelper(E[] data, int left, int right) 
	{
		//このメソッド内の仕事が分かりません。
	}
}

timSortHelper内をどのように書けば良いのでしょうか。
よろしくお願いします。

Comments

[dice142]

「どのように書けばよいでしょうか」との質問ですが、ご自身でお書きになってますよね？　どうなってほしいか、現状どうなっているのかを記載されると回答が得られやすいかと思います。

[dice142]

いや、コードを消すのではなくて、書いてみたコードでどうなるのかとか、結果はどうなって欲しいかとかそういう情報を追記していただきたかったのですが。