title: Time complexity for Shell sort?
body: <p>First, here's my Shell sort code (using Java):</p>
  
  <pre><code>public char[] shellSort(char[] chars) {
      int n = chars.length;
      int increment = n / 2;
      while(increment &gt; 0) {
          int last = increment;
          while(last &lt; n) {
              int current = last - increment;
              while(current &gt;= 0) {
                  if(chars[current] &gt; 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;
  }
  </code></pre>
  
  <p>Is this a correct implementation of Shell sort (forgetting for now about the most efficient gap sequence - e.g., 1,3,7,21...)? I ask because I've heard that the best-case time complexity for Shell Sort is O(n). (See <a href="http://en.wikipedia.org/wiki/Sorting_algorithm" rel="nofollow">http://en.wikipedia.org/wiki/Sorting_algorithm</a>). I can't see this level of efficiency being realized by my code. If I added heuristics to it, then yeah, but as it stands, no.</p>
  
  <p>That being said, my main question now - I'm having difficulty calculating the Big O time complexity for my Shell sort implementation. I identified that the outer-most loop as O(log n), the middle loop as O(n), and the inner-most loop also as O(n), but I realize the inner two loops would not actually be O(n) - they would be much less than this - what should they be? Because obviously this algorithm runs much more efficiently than O((log n) n^2).</p>
  
  <p>Any guidance is much appreciated as I'm very lost! :P</p>