title: Insert into an already-sorted list
body: <p>With Java, I have a class, known as TestClass, which has a member named Name, which is a string. I also have an ArrayList of this type, which is already sorted alphabetically by Name. What I want to do is find the best index in which to put a new instance of TestClass. The best approach I could come up with so far is this:</p>
  
  <pre><code>public static int findBestIndex(char entry, ArrayList&lt;TestClass&gt; list){
      int desiredIndex = -1;
      int oldPivot = list.size();
      int pivot = list.size()/2;
      do
      {
          char test = list.get(pivot).Name.charAt(0);
          if (test == entry)
          {
              desiredIndex = pivot;
          }
          else if (Math.abs(oldPivot - pivot) &lt;= 1)
          {
              if (test &lt; entry)
              {
                  desiredIndex = pivot + 1;
              }
              else
              {
                  desiredIndex = pivot - 1;
              }
          }
          else if (test &lt; entry)
          {
              int tempPiv = pivot;
              pivot = oldPivot - (oldPivot - pivot)/2;
              oldPivot = tempPiv;
          }
          else
          {
              int tempPiv = pivot;
              pivot = pivot - (oldPivot - pivot)/2;
              oldPivot = tempPiv;
          }
  
      } while (desiredIndex &lt; 0);
  
      return desiredIndex;
  }
  </code></pre>
  
  <p>Essentially, Break the array in half, check to see if your value goes before, after, or at that point. If it's after, check the first half of the array. Other wise, check the second half. Then, repeat. I understand that this method only tests by the first character, but that's easily fixed, and not relevant to my main problem. For some scenarios, this approach works well enough. For most, it works horribly. I assume that it isn't finding the new pivot point properly, and if that's the case, how would I fix it?</p>
  
  <p>Edit: For clarification, I'm using this for an inventory system, so I'm not sure a LinkedList would be appropriate. I'm using an ArrayList because they are more familiar to me, and thus would be easier to translate into another language, if needed (which is likely, at the moment, might be moving over to C#). I'm trying to avoid things like Comparable for that reason, as I'd have to completely re-write if C# lacks it.</p>
  
  <p>Edit part Duex: Figured out what I was doing wrong. Instead of using the previous pivot point, I should have been setting and changing the boundaries of the area I was checking, and creating the new pivot based on that.</p>