Comp 388 Lab 2: insertion sort and mergesort

Comp 388 lab 2 - insertion sort and mergesort

A Race of Sorts

Goals

implement in-place insertion sort, following Bailey
implement either recursive or non-recursive mergesort
more timing comparisions

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:

sort each half, recursively
merge the results

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 1024 or 131072 or 1048576). It can be used with either the recursive or nonrecursive forms.

The non-recursive mergesort, imsort(), requires one change to activate: you have to edit mergepass so that it does something. For example, mergepass(A, temp, 16) should:

call mergeblocks (A,temp, 0, 16), to merge the blocks A[0-15] and A[16-31] into temp[0-31]
call mergeblocks (A,temp, 32, 16), to merge the blocks A[32-47] and A[48-63] into temp[32-63]
call mergeblocks (A,temp, 64, 16), to merge the blocks A[64-79] and A[80-95] into temp[64-95]
...
end when the end of the array is reached

The main program then calls this with successive block sizes 2, 4, 8, 16, 32, ... until the blocksize becomes larger than the entire array size. It all boils down to the following, sort of in order:

merge pairs of adjacent single elements to form sorted blocks of length 2
merge pairs of adjacent sorted blocks of length 2 to form sorted blocks of length 4
merge pairs of adjacent sorted blocks of length 4 to form sorted blocks of length 8
....

Mergesort can also be done recursively; we'll discuss that in class.

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.