Performance estimation of shellSort

68 Views Asked by At

I'm trying to make a performance estimation for shell-sort algorithm. And I fail in it.

My formula:

enter image description here

equals to

enter image description here

where dz is outer while-loop, dy is middle for-loop, and dx is inner for-loop (sdee code below)

Should be:

enter image description here

Question: what's wrong in my shell sort estimation via integrals?

Shell Sort implementation (Java):

public static void shellSort(Comparable[] array) {
    int N = array.length;
    int h = 1;
    while (h < N / 3) h = 3 * h + 1;
    while (h >= 1) { //outer loop (dz)
        for (int i = h; i < N; i++) { //middle loop (dy) 
            for (int j = i; j >= h; j -= h) { //inner loop (dx)
                if (array[j].compareTo(array[j - h]) < 0) swap(array, j, j - h);
            }
        }
        h = h / 3;
    }
}