title: C++ - Fastest way to add an item to a sorted array
body: <p>I've got a database with approximately 200 000 items, which is sorted by username. Now when I add an item to end of array and call my quick sort function to sort that array it takes almost a second to sort, which is not acceptable. There are definitely quite some optimisations that can be done. For example if I sequentially compare each string from n-1 to 0, and then move items accordingly performance is much greater.</p>
  
  <p>Other idea is that I could perform binary search from 0 to n-1, well not infact search, but something similar to take advantage of my already sorted array. However I've failed to write a proper function that would return an index where my new element should be placed.</p>
  
  <pre><code>void quick_sort(int left, int right)
  {
      int i = left, j = right;
      if (left &gt;= right) return;
      char  pivotC[128];
      DataEntry *tmp;
  
      strcpy_a(pivotC, sizeof pivotC, User[(left + right) / 2]-&gt;username);
  
      while (i &lt;= j)
      {
          while (StringCompare(User[i]-&gt;username, pivotC))
              i++;
          while (StringCompare(pivotC, User[j]-&gt;username))
              j--;
          if (i &lt;= j) 
          {
              tmp = User[i];
              User[i] = User[j];
              User[j] = tmp;
              i++;
              j--;
          }
      }
      if (left &lt; j)
          quick_sort(left, j);
      if (i &lt; right)
          quick_sort(i, right);
  }
  </code></pre>
  
  <p>Any help is greatly appreciated.</p>