title: What is the benefit of Shell Sort versus Insertion/Bubble Sort?
body: <p>My professor gave me the following definition of Shell Sort. I've included the Bubble and Insertion Sort algorithms as well.</p>
  
  <p>What is the advantage of using Shell Sort vs just a regular Insertion Sort or Bubble Sort with <code>gap=1</code>? Eventually, the Shell Sort boils down to that anyway, right?</p>
  
  <p>I'm not asking you to do my homework. I'm legitimately confused and want to understand what's going on.</p>
  
  <p>Also, I've already visited Wikipedia and seen the Time Complexity table and I already know what they say. I'm looking for the <em>why</em>, not the <em>what</em>.</p>
  
  <pre><code>def shell(a, n):
      gap = n / 2
  
      while gap &gt;= 1:
              insertion(a, n, gap) # or bubble
              gap /= 2
  
  def bubble(a, n, gap=1):
      for i in range(n):
              for j in range(n-i-gap):
                      if a[j] &gt; a[j+gap]:
                              swap(a, j, j+1)
  
  def insertion(a, n, gap=1):
      for i in range(1,n):
              x = a[i]
              j = i-gap
  
              while j&gt;=0 and  a[j]&gt;x:
                      a[j+gap] = a[j]
                      j-=gap
  
              a[j+gap]=x
  </code></pre>