Comp 388 lab 2 - insertion sort and mergesort

A Race of Sorts

Goals

Overview

You should take my IntList class, IntList.cs, and add the sorting methods. Then make some measurements. I've left out the expand() method from IntList, 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. After you run your sort method, you can check that it worked with A.checksort().

I've left my selection-sort implementation in place, in A.ssort(). It uses Stopwatch to make timing measurements.

To run things, modify the sort.cs file. It's set up to allow specification of LISTSIZE on the command line, but if you run this from within Xamarin then it may be easier to change the default value and recompile each time.

No C++ is used!

Insertion Sort

This is pretty well described in Bailey, section 6.3, page 125. Implement it as IntList.isort(). Include the Stopwatch.

Merge Sort

This is in Bailey section 6.4. The recursive version works like this:

You may either implement the recursive or non-recursive versions. I've created a starter method for the non-recursive version.

I have supplied a mergeblocks(int[] A, int[] T, int start, int blocksize) method to merge two consecutive blocks into one. It should take care of odd leftovers, but if you have problems then try switching to an array with size an exact power of 2 (like 131072 or 1048576). It can be used with either the recursive or nonrecursive forms.

How can mergesort be done nonrecursively? If you examine what is "really going on" in the recursive version, it all boils down to the following, sort of in order:
One way to describe the loop to mergesort array A nonrecursively is the following:
    blockLength = 1;
    while (blockLength < A.length) {
          merge pairs of adjacent sorted blocks of length blockLength
          blockLength = blockLength * 2;
    }

With either the recursive or the nonrecursive version you will need a second array, T or temp, to do the merges into. At the end of each pass, you can copy back into A, or you can simply swap A (corresponding to IntList.elements) and temp:
        int[] a = elements;
        elements = temp;
        temp = a;
as is done in the stub imsort() method.

Timing Comparisons

First, try comparing selection sort and insertion sort for sizes up to about 100,000.

Then try comparing the winner above with mergesort, for sizes up to as long as you have patience for. Mergesort should be much faster.

Finally, find out how large an array you can sort with mergesort in 10 seconds. Does the timing seem to fit the O(N log(N)) model?

You really should use checksort() to verify that your sort implementation works. I will.

To submit your project, create a zipfile and email it to me at pld@cs.luc.edu, or use sakai.