Primero, aquí está mi código de clasificación de Shell (usando Java):

public char[] shellSort(char[] chars) {
    int n = chars.length;
    int increment = n / 2;
    while(increment > 0) {
        int last = increment;
        while(last < n) {
            int current = last - increment;
            while(current >= 0) {
                if(chars[current] > chars[current + increment]) {
                    //swap
                    char tmp = chars[current];
                    chars[current] = chars[current + increment];
                    chars[current + increment] = tmp;
                    current -= increment;
                }
                else { break; }
            }
            last++;
        }
        increment /= 2;
    }
    return chars;
}

¿Es esta una implementación correcta de la clasificación de Shell (olvidando por ahora la secuencia de brecha más eficiente, por ejemplo, 1,3,7,21 ...)? Lo pregunto porque he escuchado que la complejidad del mejor momento para Shell Sort es O (n). (Verhttp://en.wikipedia.org/wiki/Sorting_algorithm). No puedo ver este nivel de eficiencia realizado por mi código. Si le agrego heurística, entonces sí, pero tal como está, no.

Dicho esto, mi pregunta principal ahora es que tengo dificultades para calcular la complejidad del tiempo de Big O para mi implementación de Shell. Identifiqué que el bucle más externo como O (log n), el bucle medio como O (n) y el bucle más interno también como O (n), pero me doy cuenta de que los dos bucles internos no serían realmente O ( n) - serían mucho menos que esto, ¿qué deberían ser? Porque, obviamente, este algoritmo se ejecuta mucho más eficazmente que O ((log n) n ^ 2).

Cualquier orientación es muy apreciada ya que estoy muy perdido! :PAG