CSci 2101 Lab 9: Merge sort

Work in pairs or groups of 3 on this lab.

Task 1: Testing and implementing merge sort (30 points)

Your task is to write tests for, and then implement, merge sort. The starting files are given below. Note that there is a testing file with main that tests random data and also a JUnit file that runs small-scale tests. Both are needed as they test different properties of the data.
Write JUnit tests for merge sort before you implement it. You can reuse the arrays that are defined. Random tests are already written.

public class SortingMethods {
	/**
	 * The method sorts an array using insertion sort
	 * @param <T> - the type of elements in the array (must extend Comparable<T>)
	 * @param arr - the array to be sorted
	 */
	public static <T extends Comparable<T>> void insertionSort(T [] arr) {
			
		for (int i = 1; i < arr.length; ++i) {
			// loop invariant: arr[0..i-1] is sorted
			
			// the item to be inserted into the proper 
			// position in the sorted portion of the array
			T nextItem = arr[i];
			
			// iterating through the sorted portion backward
			int j = i;
			while (j > 0 && arr[j-1].compareTo(nextItem) > 0){
				// loop invariant: nextItem is smaller than
				// elements to the left of it
				
				//shift arr[j-1] to the right
				arr[j] = arr[j-1];
				j--;
			}
			// insert the new item into its position
			arr[j] = nextItem;
		}
	}
	/**
	 * The method sorts an array using merge sort. The method is recursive. 
	 * @param <T> - the type of elements in the array (must extend Comparable<T>)
	 * @param arr - the array to be sorted
	 */
	public static <T extends Comparable<T>> void mergeSort(T [] arr) {
		if (arr.length > 1) {
			// split the array into two halves
			int length1 = arr.length/2;
			int length2 = arr.length - arr.length/2;
			
			// create the arrays: 
			T[] half1 = (T[]) new Comparable[length1];
			T[] half2 = (T[]) new Comparable[length2];
			
			// copy the corresponding portions of the array into new arrays
			for(int i = 0; i<length1; i++) {
				half1[i] = arr[i];
			}
			
			for(int i = length1; i < arr.length; i++) {
				half2[i - length1] = arr[i];
			}
			
			// fill in the rest of your code here
		}
	}
	
	
}


import java.util.Random;

public class TestSorting {
	public static void main(String [] args) {
		// the array must be of Integer, not int,
		// otherwise it's not recognized as Comparable
		System.out.println("======== Testing random array generating ==========");
		Integer [] toSort = randomInts(1, 101, 20);
		printIntArray(toSort);
		System.out.println(isSorted(toSort));
		
		System.out.println("======== Testing insertion sort ==========");
		
		// small-scale test: print elements
		toSort = randomInts(1,101, 10);
		System.out.println("Before sorting: ");
		printIntArray(toSort);
		System.out.println("After sorting: ");
		SortingMethods.insertionSort(toSort);
		printIntArray(toSort);
		
		// larger-scale test: run on several arrays and check if they
		// are sorted
		boolean allSorted = true;
		for (int i = 0; i < 5; ++i) {
			toSort = randomInts(1, 101, 20 * (i + 1));
			SortingMethods.insertionSort(toSort);
			boolean isSorted = isSorted(toSort);
			allSorted = allSorted && isSorted;
			System.out.println("An array of " + 20 *(i + 1) + " elements is sorted: " + isSorted);
			if (!isSorted) {
				System.out.println("This array was not sorted properly:");
				printIntArray(toSort);
			}
		}
		if (allSorted) {
			System.out.println("Congratulations! Your insertion sort is working!");
		} else {
			System.out.println("There are problems with your insertion sort");
		}
		
		System.out.println("======== Testing merge sort ==========");
		
		toSort = randomInts(1,101, 11);
		System.out.println("Before sorting: ");
		printIntArray(toSort);
		System.out.println("After sorting: ");
		SortingMethods.mergeSort(toSort);
		printIntArray(toSort);
		
		allSorted = true;
		for (int i = 0; i < 5; ++i) {
			toSort = randomInts(1, 101, 20 * (i + 1));
			SortingMethods.mergeSort(toSort);
			boolean isSorted = isSorted(toSort);
			allSorted = allSorted && isSorted;
			System.out.println("An array of " + 20 *(i + 1) + " elements is sorted: " + isSorted);
			if (!isSorted) {
				System.out.println("This array was not sorted properly:");
				printIntArray(toSort);
			}
		}	

		if (allSorted) {
			System.out.println("Congratulations! Your merge sort is working!");
		} else {
			System.out.println("There are problems with your merge sort");
		}
		
	}
	
	/**
	 * Generates an array of random Integers in the range from 
	 * min (inclusive) to max (exclusive). The number of elements 
	 * is given by num. 
	 * @param min - the minimum value (inclusive)
	 * @param max - the maximum value (exclusive)
	 * @param num - the number of elements in the array
	 * @return - the array of num random Integers between min and max
	 * @throws IllegalArgumentException if min >= max or num < 0
	 */
	public static Integer [] randomInts(int min, int max, int num) {
		if (min >= max || num < 0) {
			throw new IllegalArgumentException();
		}
		Integer [] theInts = new Integer[num];
		Random rand = new Random();
		for (int i = 0; i < num; ++i){
			theInts[i] = rand.nextInt(max - min) + min;			
		}
		return theInts;
	}
	
	/**
	 * Checks if the parameter array is sorted
	 * @param <T> - the type of the elements in the array. Must
	 * extend Comparable<T>
	 * An array is sorted if for every two consecutive elements 
	 * arr[i].compareTo(arr[i+1]) <= 0
	 * @param arr - the given array
	 * @return true if the given array is sorted, false otherwise
	 */
	public static <T extends Comparable<T>> boolean isSorted(T [] arr) {
		for (int i = 0; i < arr.length - 1; ++i) {
			if (arr[i].compareTo(arr[i+1]) > 0 ) {
				return false; 
			}
		}
		
		return true;
	}
	
	/**
	 * 
	 * The method prints its argument <code>arr</code>
	 * element by element on one line, separated by commas,
	 * with [ before the first element and ] after the last one 
	 * @param arr - an array of type Integer
	 */
	public static void printIntArray(Integer [] arr) {
		System.out.print("[");
		for (int i = 0; i < arr.length; ++i) {
			System.out.print(arr[i]);
			if (i != arr.length - 1)
				System.out.print(", ");
		}
		System.out.println("]");
	}

}


import static org.junit.Assert.assertArrayEquals;
import org.junit.Before;
import org.junit.Test;


public class UnitTestingSorting {
	String [] strings = {"cherry", "kiwi", "pear", "apple", "avocado", "tomato"};
	String [] sortedStr = {"apple", "avocado", "cherry", "kiwi", "pear", "tomato"};
	Integer [] numbers = {7, 0, 5, 4, 4, 2, 1, 9, 2, 3, 7, 6, 5};
	Integer [] sortedNumbers = {0, 1, 2, 2, 3, 4, 4, 5, 5, 6, 7, 7, 9}; 
	
	@Test
	public void insertionSortStrings() {
		SortingMethods.insertionSort(strings);
		assertArrayEquals(sortedStr, strings);
	}
	
	@Test
	public void insertionSortIntegers() {
		SortingMethods.insertionSort(numbers);
		assertArrayEquals(sortedNumbers, numbers);
	}
	
}

How to submit:

Send me your code. CC your partner if you worked in a pair.


CSci 2101 course web site.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.