package sort; public abstract class InsertionSort { protected abstract int compare(Object o1, Object o2); private void insert(int i, Object[] data) { if (i < data.length - 1) { if (compare(data[i], data[i + 1]) > 0) { Object tmp = data[i]; data[i] = data[i + 1]; data[i + 1] = tmp; insert(i + 1, data); } } } /* * array is sorted in the following way : * * at the end of each step i, the array is sorted from index i to index n-1, * where n denotes the length of the array. * * Thus, at the beginning of the ith step, the array is sorted from index i+1 to * n. Then, we introduce the element at index i and we swap it with the next * element if it is greater than it. We repeat swapping unless the new * element is at its right place. */ public void doSort(Object[] a) { for (int i = a.length - 2; i >= 0; --i) { insert(i, a); } } }