title: Time complexity of shell sort
body: <p>In my textbook <code>Algorithms</code>, I read that : </p>
  
  <blockquote>
    <p>No mathematical results are available about the average-case number of
    compares for shellsort for randomly ordered input. Increment sequences
    have been devised that drive the asymptotic growth of the worst-case
    number of compares down to N 4/3, N 5/4, N 6/5, . . . , but many of
    these results are primarily of academic interest because these
    functions are hard to distinguish from one another (and from a
    constant factor of N ) for practical values of N.</p>
  </blockquote>
  
  <p>And, here in <a href="http://bigocheatsheet.com/" rel="nofollow">bigocheatsheet.com</a>, it is given that the Time complexity of Shell sort as :</p>
  
  <ul>
  <li>Worst case : <code>O((nlog(n))^2)</code></li>
  <li>Average    : <code>O((nlog(n))^2)</code></li>
  <li>Best case :  <code>O(n)</code></li>
  </ul>
  
  <p>And, here is my implementation of shell sort:</p>
  
  <pre><code>/**
   * Java program to implement shell sort
   */
  public class Solution
  {
      private static final int arr[] = {2,5,4,3,7,8,9,1,6,6};
      public static void main(String[] args)
      {
          final int N = arr.length;
          int h = 1;
          while(h&lt;(N/3))
              h = 3*h + 1;
  
          while(h&gt;=1)
          {
              for(int i=h;i&lt;N;i++)
              {
                  for(int j=i;j&gt;=h &amp;&amp; (arr[j-h]&gt;arr[j]);j-=h)
                  {
                      int temp = arr[j-h];
                      arr[j-h] = arr[j];
                      arr[j] = temp;
                  }
              }
  
              h=h/3;
          }
  
          for(int x:arr)
              System.out.println(x);
      }
  
  }
  </code></pre>
  
  <p>Now the problem is, I cannot understand how the worst case complexity of Shell sort comes to  <code>O((nlog(n))^2)</code> . Please correct me if I did anything wrong.</p>