Cheating

Some of you submitted copied code.  You will not receive credit for this unless you meet with us and demonstrate understanding of the code.

Scoring

We were very lenient grading the code this time around.  If your code sorts successfully and implements a bottom-up merge sort, you were given almost full credit of 4/5.  A proper analysis of the running time was worth 1/5 points. 

Solutions

Attached is an example of a functioning BUMS (IterativeMergeSort.java).  Testing your sort used the below JUnitTest (also attached)

import static org.junit.Assert.*;

import java.util.Arrays;
import java.util.Random;

import org.junit.Test;

public class JUnitTest
{

    @Test
    public void test()
    {
        int size = 1000;
    
        //initialize an array to test
        //populate with pseudo-random elements
        Integer[] myArray = new Integer[size];
        //int[] myArray = new int[size];
        Random rand = new Random();
        for(int i = 0; i < size; i++)
            myArray[i] = rand.nextInt(3*size) + 1;
        
        //copy the array over and sort them using Arrays.sort
        Integer[] expectedArray = myArray.clone();
        //int[] expectedArray = myArray.clone();
        Arrays.sort(expectedArray);
        
        //using your sort
        YOUR_SORT_GOES_HERE(myArray);
        
        //assertion failure
        assertArrayEquals(expectedArray, myArray);
    }
}

Attached is also a version of iterative merge sort that follows the guidelines of the assignment strictly (named BUMS.java)