Merge Sort

package iteration;

public interface Iterable {
    public Iterator iterator();
}

package dataStructures;

import iteration.Iterable;

public interface List extends Iterable {
    public void insert(int index, Object value)
            throws IndexOutOfBoundsException;
    public void add(Object value);
    public Object delete(int index) throws IndexOutOfBoundsException;
    public boolean delete(Object value);
    public void clear();
    public Object set(int index, Object value)
            throws IndexOutOfBoundsException;
    public Object get(int index) throws IndexOutOfBoundsException;
    public int indexOf(Object value);
    public boolean contains(Object value);
    public int size();
    public boolean isEmpty();
}

package sorting;

import dataStructures.List;

public interface ListSorter {
    public List sort(List list);
}

public class ArrayIterator implements Iterator {
    private final Object[] _array;
    private final int _first;
    private final int _last;
    private int _current = -1;

    public ArrayIterator(Object[] array, int start, int length) {
        assert array != null : "array can’t be null";
        assert start >= 0 : "start can’t be < 0";
        assert start < array.length : "start can’t be > array.length";
        assert length >= 0 : "length can’t be < 0";
        _array = array;
        _first = start;
        _last = start + length - 1;
        assert _last < array.length : "start + length can’t be > array.length";
    }

    public ArrayIterator(Object[] array) {
        assert array != null : "array can’t be null";
        _array = array;
        _first = 0;
        _last = array.length - 1;
    }

    public void first() {
        _current = _first;
    }

    public void last() {
        _current = _last;
    }

    public void next() {
        ++_current;
    }

    public void previous() {
        --_current;
    }

    public boolean isDone() {
        return _current < _first || _current > _last;
    }

    public Object current() throws IteratorOutOfBoundsException {
        if (isDone()) {
            throw new IteratorOutOfBoundsException();
        }
        return _array[_current];
    }
}

package iteration;

public class IteratorOutOfBoundsException extends RuntimeException {
}

package sorting;

import dataStructures.ArrayList;
import dataStructures.List;
import iteration.Iterator;

public class MergesortListSorter implements ListSorter {
    private final Comparator _comparator;

    public MergesortListSorter(Comparator comparator) {
        assert comparator != null : "comparator cannot be null";
        _comparator = comparator;
    }

    public List sort(List list) {
        assert list != null : "list cannot be null";
        return mergesort(list, 0, list.size() - 1);
    }

    private List mergesort(List list, int startIndex, int endIndex) {
        if (startIndex == endIndex) {
            List result = new ArrayList();
            result.add(list.get(startIndex));
            return result;
        }
        int splitIndex = startIndex + (endIndex - startIndex) / 2;
        List left = mergesort(list, startIndex, splitIndex);
        List right = mergesort(list, splitIndex + 1, endIndex);
        return merge(left, right);
    }

    private List merge(List left, List right) {
        List result = new ArrayList();
        Iterator l = left.iterator();
        Iterator r = right.iterator();
        l.first();
        r.first();
        while (!(l.isDone() && r.isDone())) {
            if (l.isDone()) {
                result.add(r.current());
                r.next();
            } else if (r.isDone()) {
                result.add(l.current());
                l.next();
            } else if (_comparator.compare(l.current(), r.current()) <= 0) {
                result.add(l.current());
                l.next();
            } else {
                result.add(r.current());
                r.next();
            }
        }
        return result;
    }
}