Implement and test the Merge Sort algorithm using the Iterator and
Comparable interfaces. The Iterator interface is in the student
support code and Comparable is in the Java standard library. The
support code is in the following github repository.
https://github.com/IUDataStructuresCourse/merge-sort-student-support-code
You will submit both your implementation and your tests to the same autograder .
Define a public MergeSort class in MergeSort.java with the
following method:
public static <E extends Comparable<? super E>>
void sort(Iterator<E> begin, Iterator<E> end);
The begin and end iterators represent the half-open range
[begin,end) of a sequence. After the call to sort, the range
[begin,end) should contain the same elements as before, but sorted
from low to high according to the Comparable ordering.
The iterators begin and end should not be mutated, but of course
you can clone them and mutate the clones.
Specification: Let S be the unsorted sequence represented by the begin and end iterators,
and call S_sorted the value of S after sort is called. The following must hold.
(Ordering) If the sorted sequence is traversed from begin to end using successive calls to Iterator.next(), then for every two consecutive elements a, b, we have a.compareTo(b) <= 0.
(Permutation) For any element x, it appears the same number of times in S as in S_sorted
The Merge Sort algorithm relies on the Merge algorithm, which you should implement with the following method:
public static <E extends Comparable<? super E>>
Iterator<E> merge(Iterator<E> begin1, Iterator<E> end1,
Iterator<E> begin2, Iterator<E> end2,
Iterator<E> result);
Prior to the call to merge, the input ranges [begin1,end1) and
[begin2,end2) must be sorted. Let n be the number of elements in
the first range and m be the number of elements in the second range.
The elements from both ranges are written to the range
[result,result.advance(n+m)) in such a way that the result is in
sorted order. The merge function should return an iterator for the
position result.advance(n+m). All of the iterator parameters
(begin1, end1, etc.) should not be mutated directly, but you can
clone them and mutate the clones.
Create file test/StudentTest.java, which contains public class StudentTest.
Create your unit tests as methods of test/StudentTest.java. If you come up
with your own test properties, those functions for test properties should go in
test/StudentTest.java as well.
The StudentTest class should contain a member function
public void test() (marked with @Test) which serves as the main entrance.
For example, if you have 2 test functions test_find_foo() and test_find_bar(),
the test() function should be:
@Test
public void test() {
test_find_foo();
test_find_bar();
}