3.2. Comparison-based Sort

public class SelectionSort<T extends Comparable<T>> extends AbstractSort<T> {
    public SelectionSort() {
        this(Comparator.naturalOrder());
    }

    public SelectionSort(Comparator<T> comparator) {
        super(comparator);
    }
}

@Override
public void sort(T[] array, final int beginIndex, final int endIndex) {
    for (int i = endIndex; i > beginIndex; i--) {
        int max = beginIndex;

        for (int j = beginIndex + 1; j < i; j++) {
            if (compareTo(array, j, max) > 0)
                max = j;
        }

        swap(array, max, i - 1);
    }
}

public class HeapSort<T extends Comparable<T>> extends AbstractSort<T> {
    public HeapSort() {
        this(Comparator.naturalOrder());
    }

    public HeapSort(Comparator<T> comparator) {
        super(comparator);
    }
}

private void sink(T[] array, int k, int beginIndex, int endIndex) {
    for (int i = getLeftChildIndex(beginIndex, k); i < endIndex; k = i, i = getLeftChildIndex(beginIndex, k)) {
        if (i + 1 < endIndex && compareTo(array, i, i + 1) < 0) i++;
        if (compareTo(array, k, i) >= 0) break;
        swap(array, k, i);
    }
}

private int getParentIndex(int beginIndex, int k) {
    return beginIndex + (k - beginIndex - 1) / 2;
}

private int getLeftChildIndex(int beginIndex, int k) {
    return beginIndex + 2 * (k - beginIndex) + 1;
}

@Override
public void sort(T[] array, int beginIndex, int endIndex) {
    // heapify all elements
    for (int k = getParentIndex(beginIndex, endIndex - 1); k >= beginIndex; k--)
        sink(array, k, beginIndex, endIndex);

    // swap the endIndex element with the root element and sink it
    while (endIndex > beginIndex + 1) {
        swap(array, beginIndex, --endIndex);
        sink(array, beginIndex, beginIndex, endIndex);
    }
}

public class InsertionSort<T extends Comparable<T>> extends AbstractSort<T> {
    public InsertionSort() {
        this(Comparator.naturalOrder());
    }

    public InsertionSort(Comparator<T> comparator) {
        super(comparator);
    }
}

protected void sort(T[] array, int beginIndex, int endIndex, final int h) {
    int begin_h = beginIndex + h;

    for (int i = begin_h; i < endIndex; i++)
        for (int j = i; begin_h <= j && compareTo(array, j, j - h) < 0; j -= h)
            swap(array, j, j - h);
}

@Override
public void sort(T[] array, int beginIndex, int endIndex) {
    sort(array, beginIndex, endIndex, 1);
}

public abstract class ShellSort<T extends Comparable<T>> extends InsertionSort<T> {
    protected List<Integer> sequence;

    public ShellSort(Comparator<T> comparator) {
        super(comparator);
        sequence = new ArrayList<>();
        populateSequence(10000);
    }
}

/**
 * Populates the gap sequence with respect to the size of the list.
 * @param n the size of the list to be sorted.
 */
protected abstract void populateSequence(int n);

/**
 * @param n the size of the list to be sorted.
 * @return the starting index of the sequence with respect to the size of the list.
 */
protected abstract int getSequenceStartIndex(int n);

@Override
 public void sort(T[] array, int beginIndex, int endIndex) {
     int n = endIndex - beginIndex;
     populateSequence(n);

     for (int i = getSequenceStartIndex(n); i >= 0; i--)
         sort(array, beginIndex, endIndex, sequence.get(i));
 }

public class ShellSortKnuth<T extends Comparable<T>> extends ShellSort<T> {
    public ShellSortKnuth() {
        this(Comparator.naturalOrder());
    }

    public ShellSortKnuth(Comparator<T> comparator) {
        super(comparator);
    }
}

@Override
protected void populateSequence(int n) {
    n /= 3;

    for (int t = sequence.size() + 1; ; t++) {
        int h = (int) ((Math.pow(3, t) - 1) / 2);
        if (h <= n) sequence.add(h);
        else break;
    }
}

@Override
protected int getSequenceStartIndex(int n) {
    int index = Collections.binarySearch(sequence, n / 3);
    if (index < 0) index = -(index + 1);
    if (index == sequence.size()) index--;
    return index;
}