title: Straight and Binary insertion sort
body: <p>Hello I was asked to improve insertion sort by using binary search instead of linear. The problem is that the best case is now O(n log n) instead of O(n) due to <strong>data comparisons</strong>, which made the program if not slower in some cases equal. Here is my binary insertion sort code: </p>
  
  <pre><code>void InsertionSort(int data[], int size)
  {
      int index = -1;
      for(int i = 1,temp,j;i&lt;size;i++)
      {
          temp = data[i];//DM O(N)
          int high = i,low = 0,mid;//DM O(N)
          while(low &lt;= high)//DC O(nlogn)
          {
              mid = (low + high) /2;
              if(temp &lt; data[mid])
              {
                  high = mid - 1;
                  index = mid;
              }
  
              else if (temp &gt; data[mid])
              {
                  low = mid + 1;      
              }
  
              else if(data[mid] == temp)
              {
                  index = mid;
                  break; 
              } 
  
          }
          for(j = i;j &gt; index;j--)
          {
              data[j] = data[j-1];//DC Worst Case O(n*n) but the exact is summation of n(n+1) / 2 nad best case o(1)
          }
          data[j] = temp;//DM O(n)
      }   
  }
  </code></pre>