title: Implementing a binary insertion sort using binary search in Java
body: <p>I'm having trouble combining these two algorithms together. I've been asked to modify <code>Binary Search</code> to return the index that an element should be inserted into an array. I've been then asked to implement a <code>Binary Insertion Sort</code> that uses my <code>Binary Search</code> to sort an array of randomly generated <code>ints</code>.</p>
  
  <p>My <code>Binary Search</code> works the way it's supposed to, returning the correct index whenever I test it alone. I wrote out <code>Binary Insertion Sort</code> to get a feel for how it works, and got that to work as well. As soon as I combine the two together, it breaks. I know I'm implementing them incorrectly together, but I'm not sure where my problem lays.</p>
  
  <p>Here's what I've got:</p>
  
  <pre><code>public class Assignment3
  {
      public static void main(String[] args)
      {   
          int[] binary = { 1, 7, 4, 9, 10, 2, 6, 12, 3, 8, 5 };
  
          ModifiedBinaryInsertionSort(binary);
  
      }
  
      static int ModifiedBinarySearch(int[] theArray, int theElement)
      {
          int leftIndex = 0;
          int rightIndex = theArray.length - 1;
          int middleIndex = 0;
  
          while(leftIndex &lt;= rightIndex)
          {
              middleIndex = (leftIndex + rightIndex) / 2;
  
              if (theElement == theArray[middleIndex])
                  return middleIndex;
              else if (theElement &lt; theArray[middleIndex])
                  rightIndex = middleIndex - 1;
              else
                  leftIndex = middleIndex + 1;
          }
  
          return middleIndex - 1;
      }
  
      static void ModifiedBinaryInsertionSort(int[] theArray)
      {
          int i = 0;
          int[] returnArray = new int[theArray.length + 1];
  
          for(i = 0; i &lt; theArray.length; i++)
          {
              returnArray[ModifiedBinarySearch(theArray, theArray[i])] = theArray[i];
          }
  
          for(i = 0; i &lt; theArray.length; i++)
          {
              System.out.print(returnArray[i] + " ");
          }
      }
  }
  </code></pre>
  
  <p>The return value I get for this when I run it is <code>1 0 0 0 0 2 0 0 3 5 12</code>. Any suggestions?</p>
  
  <p>UPDATE: updated ModifiedBinaryInsertionSort</p>
  
  <pre><code>static void ModifiedBinaryInsertionSort(int[] theArray)
  {
      int index = 0;
      int element = 0;
      int[] returnArray = new int[theArray.length];
  
      for (int i = 1; i &lt; theArray.lenght - 1; i++)
      {
          element = theArray[i];
          index = ModifiedBinarySearch(theArray, 0, i, element);
          returnArray[i] = element;
  
          while (index &gt;= 0 &amp;&amp; theArray[index] &gt; element)
          {
              theArray[index + 1] = theArray[index];
              index = index - 1;
          }
          returnArray[index + 1] = element;
      }
  }
  </code></pre>