private void sortWithMedianOf3PartitioningAndSentinelsAndCutoff(
			T[] a, int lo, int hi)
	{
		if (hi - lo + 1 <= CUTOFF)
		{
			Sorter<T> insertionSorter = new InsertionSorter<>();
			insertionSorter.sort(a, lo, hi);
			return;
		}

		int mid = lo + (hi - lo) / 2; // mid has to be calculated relative to lo

		/*
		 * The partitioning is most efficient if the partitioning element
		 * divides the array into equal halves. There is a greater probability
		 * of achieving this if a median is used instead of the first element
		 * being picked as the partitioning element.
		 * 
		 * Here the median is calculated using 3 random elements. Picking the
		 * first, last and middle element as sample elements is random enough.
		 */

		/*
		 * Calculation of median. As a bonus, use the sample items(the element
		 * greater then and lesser than the median) as sentinels at the ends of
		 * the array and remove both array bounds tests in partition().
		 */

		// place the lowest element at lo
		compexch(a, lo, mid);
		compexch(a, lo, hi);

		// place the median at mid and the highest at hi
		compexch(a, mid, hi);

		// now place it at lo + 1
		exch(a, mid, lo + 1); // the median(in terms of the position) is
								// now the partitioning element

		// To eliminate the test against the right array. Also read the note above
		//exch(a, max(a), a.length - 1); 
		
		int j = partitionWithSentinels(a, lo + 1, hi - 1); // Partition
		// Sort left part a[lo..j-1].
		sortWithMedianOf3PartitioningAndSentinelsAndCutoff(a, lo, j - 1);
		// Sort right part a[j+1..hi].
		sortWithMedianOf3PartitioningAndSentinelsAndCutoff(a, j + 1, hi);
	}