I've provided you with an IntelliJ project named sorters (as sorters.zip). In the Sorters.java class in this project, I implement most of the sorting methods of Bailey chapter 6, each declared within a class IntList which is my own implementation of an ArrayList<int>. One of the sort methods is isort(), which is an implementation of insertion sort taken straight from Bailey. There is also isort1().

You are to implement insertion sort *outside* of the IntList
class, that is, in my SortTester.java file. Your function should take
either an IntList and return an ArrayList<Integer> that represents a
sorted copy of the original list. The original list is not to be modified.
You are, instead, to use the ArrayList methods get()
and add(). You will also use
IntList.get(), to access the
original list. For example, my version takes an IntList IL as parameter
and has the following inner loop to find the position where value next
= elements[k] is to be inserted into ArrayList<Integer>
results, where k ranges over 0 to IL.size() in the outer loop:

while (i
>= 0 && results.**get**(i) > next) {

i --;

}

My code also includes the following to insert the value next into results. The two-parameter form of add() shifts everything from position i+1 to the end of the array up a slot.

results.add(i+1, next);

At the end, results is returned.

You can allocate all the space you will need in results with results.ensureCapacity(IL.size()). (This probably doesn't make much difference.)

How does the speed of your "external" insertion sort compare with the "internal" version?

Recursive mergesort appears in my Sorters.java file as IntList.rmsort(). The recursive approach would sort an array of length 100 by:

- dividing it into two pieces of size 50 each
- dividing each of
*those*into two pieces of size 25 each - dividing each of
*those*into two pieces of sizes 13 and 12 - ...
- (down to pieces of size 2)
- divide those pieces into two pieces of size 1,
*which are automatically sorted*. - Now do all the merges on the way back up

Iterative mergesort works differently. At any one time, you visualize the array as a sequence of "blocks", each of size a perfect power of two except for the final block. At the start, the blocksize is 1, and each block of length 1 is, of course, sorted. The process repeats with successive block sizes 2, 4, 8, 16, 32, ... until the blocksize becomes larger than the entire array size. On an array of size 100 you would now do the following:

- merge each pair of consecutive blocks of length 1 into a block of length 2
- merge each pair of consecutive blocks of length 2 into a block of length 4
- merge each pair of consecutive blocks of length 4 into a block of length 8
- ...
- as the last merge, we have one block of length 64, and a second block of length 100-64 = 36. Merge them.

I've supplied you with the following merging methods:

- mergeblocks (int[] A, int[] T, int start, int blocksize)
- mergeblocks2(int[] A, int[] T, int start, int block1size, int block2size)

T is the temp space, to be allocated at the start of imsort(). The first
merger method, mergeblocks(), merges two equal-sized blocks; the second
allows for the block sizes to be unequal. Use whichever you prefer. Both *should*
handle having an undersized block as the *last* block of the
array, but let me know if you have problems.

In class Sorters.java I've started the implementation of iterative mergesort in method imsort(). The code there is this:

public void
imsort() {

int[] temp = null; //
allocate temp; finish this!

int blockLength = 1;

while (blockLength <
elements.length) {

//mergepass(...)

//
swap elements and temp as follows:

//int
[] a = elements; // this is just a pointer, not an
allocation!

//elements = temp;

//temp = a;

blockLength *= 2;

}

}

You will have to edit this as necessary, and also edit the mergepass()
code. You should **not** change the mergeblocks() methods.
Make sure you allocate temp!

My class SortTester runs several versions of sorting algorithms on the same data, and records the time. Currently it runs InsertionSort, recursive MergeSort (Sorters.rmsort()), and Java's built-in Collections.sort(). You are to complete the definition of iterative mergesort, imsort(), and test it for speed against recursive mergesort and Collections.sort(). You will need to comment out the InsertionSort test once you've got imsort() working, as you'll need to test it with sizes much too large for InsertionSort to handle in a reasonable time.

In my definition of class IntList, I've left out the expand() method (the topic of the previous lab), but you don't need that as you're not using add(). Instead, you will create IntLists of the desired size using the constructor,

IntList A = new IntList(100000);

and then use A.RandomFill() to create random entries. My code in SortTester.java does that, and then makes

We've already compared selection sort and insertion sort. You should:

- Compare insertion sort (whichever version was faster) with mergesort
- Compare iterative mergesort with recursive mergesort

Compare insertion sort with mergesort up to the point where insertion
sort takes 10 seconds or more. Do enough measurements to convince yourself
that insertion sort is O(n^{2}), and that mergesort is not.

Finally, find out how large an array you can sort with iterative mergesort in 10 seconds.

Make sure you use checksort() to verify that your sort implementation works.

Submit your lab on Sakai.