/**

*

* @author KAKANAKOU MIGUEL

*

*/

public final class ShellSort {

/**

* Use the shell sort method to sort the given array A

*

* @param A Array of Comparable that contains the object to sort

*/

public static void sort(Comparable[] A) {

if (A == null)

return;

int h = computeMaxH(A.length);

while (h >= 1) {

hInsertionSort(A, h);

h = h / 3;

}

}

private static void hInsertionSort(Comparable[] A, int h) {

Comparable curVal;

int j;

for (int i = h; i < A.length; i = i + h) {

curVal = A[i];

j = i - h;

while ((j >= 0) && less(curVal, A[j])) {

A[j + h] = A[j];

j = j - h;

}

A[j + h] = curVal;

}

}

private static int computeMaxH(int len) {

int h = 1;

while (h < len / 3)

h = 3 * h + 1;

return h;

}

private static boolean less(Comparable a, Comparable b) {

int cmp = a.compareTo(b);

if (cmp < 0)

return true;

return false;

}

}