title: h-sorting in Shell sort
body: <p>In shell sort, <code>3h+1</code> sequence is recommended to h-sort a list using insertion sort</p>
  
  <p><code>//1, 4, 13, 40, ...</code></p>
  
  <p>Optimal formula to compute start value of <code>h</code> is one-third of <code>listsize</code>, as shown below,</p>
  
  <pre><code>int h = 1;
  while(h &lt; listSize/3){ // why N/3?
  
    h = 3*h + 1
  }
  while(h &gt;= 1){
  
    //h-sort the array
    // perform insertionSort
    h = h/3;
  }
  </code></pre>
  
  <p>Question:</p>
  
  <p>To perform shell sort, How to prove mathematically that <code>h</code>(at max) should be less than <code>listSize/3</code>?</p>