title: How to keep track of an array element after sorting in java?
body: <p>I have an array of integers, which has to be kept sorted. Therefore, after every element insertion, i call <code>Arrays.sort()</code>. In addition, I have to keep track of the last element inserted, so that I can reach it after sorting with an <code>O(1)</code> complexity.
  For example, consider the following scenario:</p>
  
  <pre><code>int[] array = new int[10];
  array[0] = 1;
  array[1] = 2;
  array[2] = 3;
  array[3] = 8;
  array[4] = 5;
  int indexAfterSort = sort(array, 4);
  </code></pre>
  
  <p><code>indexAfterSort</code> would now contain <code>3</code>.
  The <code>int sort(int[] array, int elementIndexToTrack)</code> method gets the array, and an <code>int</code> which is the index of the element to track. It returns the index of this element after the sort is complete.
  I am looking for an efficient way to achieve this, without adding to the <code>O(nlogn)</code> complexity of the sorting algorithm, usually performed by <code>Arrays.sort()</code>. Therefore I want to avoid searching for the element after sorting, with binary search for example. My last resort would be to copy the <code>Array.sort()</code> algorithm and implement the changes I need there, but there might be an easier solution.</p>