static public void
insertionSort(int a[]) {
// Re-arrange the array elements a[0..n-1]
// so they are in ascending order.
for (int i = 0; i < a.length - 1; i++) {
int gap = i + 1;
final int t = a[gap];
while ((gap > 0) && (a[gap - 1] > t)) {
a[gap] = a[gap - 1];
gap--;
}
a[gap] = t;
}
}