LAB 10 SAMPLE ANSWERS

1.
	private static <T extends Comparable<T>> void merge(T[] finalTable, T[] leftHalf, T[] rightHalf) 
	{

		int i = 0;	// index of next position to consider in leftHalf
		int j = 0;	// index of next position to consider in rightHalf
		int k = 0;	// index of next position to fill in finalTable

		// While we haven't copied all of the elements from one of the halves into the finalTable:

		while (i < leftHalf.length && j < rightHalf.length) {

			// If the next element from the left half is less than the next element from
			// the right half, copy the next element from the left half into the next position
			// in the final table. Otherwise, copy the next element from the right half into the
			// next position in the final table. 
			if (leftHalf[i].compareTo(rightHalf[j]) < 0) 
				finalTable[k++] = leftHalf[i++];
			else
				finalTable[k++] = rightHalf[j++];
		}

		// While there are still elements in the left half, copy these into the remaining positions
		// of the final table.
		while (i < leftHalf.length) 
			finalTable[k++] = leftHalf[i++];

		// While there are still elements in the right half, copy these into the remaining positions
		// of the final table.
		while (j < rightHalf.length)
			finalTable[k++] = rightHalf[j++];
	}

2.
	private static <T extends Comparable<T>> int partition(T[] table, int first, int last) 
	{

		// Select the first element in the table as the pivot
		T pivot = table[first];

		int i = first+1;	// index of next element to consider from the left side of table
		int j = last;		// index of next element to consider from the right side of table

		do {
			// Search for next element from left that is greater than the pivot
			while (i < last && pivot.compareTo(table[i]) >= 0)
				i++;

			// Search for next element from the right that is less than or equal to the pivot 
			while (pivot.compareTo(table[j]) < 0) 
				j--;

			// Swap these values as long as our two searches don't pass each other
			if (i < j) 
				swap(table, i, j);

		} while (i < j);  // Repeat until our two search indices pass each other

                // Now the table consists of:
                // the pivot
                // followed by the first partition containing elements <= pivot (not necessarily sorted)
                // followed by the second partition containing elements > pivot (not necessarily sorted)
                // Swap the pivot with the final value in the first partition

		swap(table, first, j);

		// Return the final position of the pivot 

		return j;
	}