public static void binaryInsertionSort(Comparable[] a, int lo, int hi) {
        for (int i = lo + 1; i <= (hi < lo + 7 ? hi : lo + 7); i++) {
            for (int j = i; j > lo && less(a[j], a[j-1]); j--)
                exch(a, j, j-1);
        }
        
        for (int i = lo + 8; i <= hi; i++) {
        
//        for (int i = lo + 1; i <= hi; i++) {
            if (less(a[i], a[i-1])) {
//                int k = binarySearch(a, lo, i-1);
                Comparable v = a[i];
                int lolo = lo;
                int hihi = i-1;
                int k = lo;
                while (lolo <= hihi) {
                    int mid = lolo + (hihi - lolo) / 2;
                    if (less(v, a[mid])) hihi = mid - 1;
                    else if (less(v, a[mid+1])) { k = mid+1; break;}
                    else lolo=mid+1;
                }
                
//                for (int j = i; j > k; j--) {
//                    a[j] = a[j-1];
//                }
                System.arraycopy(a, k, a, k+1, i-k);
                a[k] = v;
            }
            assert isSorted(a, lo, i);
        }
        assert isSorted(a, lo, hi);
    }