title: Gapped Insertion sort implementation
body: <p>I'm trying to pull off a gapped insertion sort in C++, known as a Library sort. I understand the concept, but I'm having trouble pulling it off going from a regular old insertion sort. I don't know how I'd account for the gaps in the array. I've been using the integer 0 to specify a gap. The code I have so far is below, which is a working insertion sort modified abit. How would you go about implementing a library sort? I went through 20 pages of google, and I have not seen a single actual example of code, in any programming language.</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include &lt;stdlib.h&gt;
  #include &lt;time.h&gt;
  #include &lt;vector&gt;
  using namespace std;
  
  vector&lt;int&gt; librarySort(int arr[20])
  {
  int j,tmp;
  vector&lt;int&gt; array;
  for (int i=0;i&lt;20;i++)
  {
      array.push_back(0);
      array.push_back(arr[i]);
  }
  for (int i=0;i&lt;40;i++) { cout &lt;&lt; array[i] &lt;&lt; ",";}
  cout &lt;&lt; endl;
  for (int i = 1; i &lt; 40; i++) 
  {
      j = i;
      while (j &gt; 0 &amp;&amp; array[j - 1] &gt; array[j]) 
      {
          tmp = array[j];
          array[j] = array[j - 1];
          array[j - 1] = tmp;
          j--;
      }
  }
  for (int i=0;i&lt;40;i++) { cout &lt;&lt; array[i] &lt;&lt; ",";}
  return array;
  }
  int main()
  {
  srand(time(0));
  int array[20]= {0};
  for (int i=0;i&lt;20;i++)
  {
      int n=rand()%19+1;
      tmp=array[i];
      array[i]=array[n];
      array[n]=tmp;
  }
  for (int i=0;i&lt;20;i++) { cout &lt;&lt; array[i] &lt;&lt; ",";}
  cout &lt;&lt; endl;
  librarySort(array);
  }
  </code></pre>