## CSci 2101 Lab 8. June 10th.

### Due Monday, June 14th at 11:59pm

### 30 points

The lab is done in pairs.

Use Eclipse in this lab. If you run into any problems or would like to
know more about it, please ask.

Please do not use the mergesort and quicksort code in the book for this lab.

#### Task 1

Finish implementing Mergesort started here. You may use the general description of mergesort on pp. 485-487, but not the code that follows.
Test it thoroughly.

#### Task 2

Write your own implementation of quicksort. You may use pseudcode and
examples on pp. 491-497 in the textbook, but don't look at the implementation
that starts on p. 498. Note that our types are somewhat different from what's
given in the book.

Because quicksort is recursive you need a recursive helper method that
indicates what portion of the array you are working on:

```
/**
* Sorts the portion of the given array arr[first..last]
* using a recursive quicksort algorithm
* @param <T> - the type of array elements (must be Comparable<T>)
* @param arr - the array to sort
* @param first - the index of the first element in the portion to be sorted
* @param last - the index of the last element in the portion to be sorted
*/
private static <T extends Comparable<T>> void quickSortRecursive(T [] arr, int first, int last)
```

This method should be called from a public method that doesn't take indices
and make the first call to the recursive method:

```
public static <T extends Comparable<T>> void quickSort(T [] arr) {
quickSortRecursive(arr, 0, arr.length-1);
}
```

Make sure to test your code extensively and summarize your testing
results.

#### How to submit

Submit
the java file with all your testing code by e-mail to me. The subject of the message
must
be **2101 Lab 8**. Make
sure to CC your group partner.

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.