When you need to add a new element to the array, create a second array, copy the contents of the original into it, and add the new element into it. Then you could use a sorting algorithm to sort the array.
You could also use <code>java.util.Arrays.sort(Object array)</code> to sort the array when ever you need it to be correctly ordered -- this assumes that your objects in the array are Comparable or that you use the version of the method that also takes a Comparator.
Actually, I guess a more efficient way to do it would be since the first array is by definition sorted, you could create the second array, and copy the elements from the first array into it as long as the elements are "less than" what you want to add. When you get to the first element in the original array that is "greater than" what you want to add, then add your element to the new array, and then copy the remainder from the original array into the new one.