Во-первых, вот мой код сортировки Shell (с использованием 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;
}

Является ли это правильной реализацией сортировки Shell (на данный момент мы забываем о наиболее эффективной последовательности пробелов - например, 1,3,7,21 ...)? Я спрашиваю, потому что слышал, что сложность времени в лучшем случае для сортировки оболочки - O (n). (Увидетьhttp://en.wikipedia.org/wiki/Sorting_algorithm). Я не вижу этого уровня эффективности, реализуемого моим кодом. Если бы я добавил к ней эвристику, то да, но в ее нынешнем виде нет.

При этом мой главный вопрос сейчас - мне трудно вычислить сложность времени Big O для моей реализации сортировки в Shell. Я определил, что самый внешний цикл как O (log n), средний цикл как O (n), а самый внутренний цикл также как O (n), но я понимаю, что внутренние два цикла на самом деле не будут O ( n) - они были бы намного меньше этого - какими они должны быть? Очевидно, что этот алгоритм работает намного эффективнее, чем O ((log n) n ^ 2).

Любое руководство очень ценится, поскольку я очень потерян! :П