Question: 1. Suppose given an array of size n, with sorted values.
2. In iteration i, a new random-generated value is given, and inserted into the end of the array.
3. The array is then resorted, and discard the least value item.
4. After iteration n, the retained array will contain the largest value items.

For example, in Java syntax, it will be something like:

```
List l = new ArrayList();
l.add(new Integer(2));
l.add(new Integer(3));
l.add(new Integer(6));
l.add(new Integer(9));

Random rand = new Random();
for (int i=0; i < n; i++) {
  l.add(new Integer(rand.nextInt(1000)));
}    
Collections.sort(l);
l.remove(0);

```

But it seems it's inefficient. Any better algorithm?

Answer: 
[**Collections.binarySearch()**](http://java.sun.com/j2se/1.4.2/docs/api/java/util/Collections.html#binarySearch(java.util.List,%20java.lang.Object))

[**ArrayList.ensureCapcity()**](http://java.sun.com/j2se/1.4.2/docs/api/java/util/ArrayList.html#ensureCapacity(int))

Your pseudocode inserts a set of new items N into sorted list A of size S and then discards the smallest item. Use **Collections.binarySearch()** to find the insertion point. *[Read the note the performance impact if your List is does not support RandomAccess. ArrayList does support RandomAccess.]*

```
List<Integer> l = new ArrayList<Integer>();
l.add(new Integer(2));
l.add(new Integer(3));
l.add(new Integer(6));
l.add(new Integer(9));

l.ensureCapacity(l.size()+n);

Random rand = new Random();
for (int i=0; i < n; i++) {
  final Integer newInt = Integer.rand.nextInt(1000);
  int insertPoint = Collections.binarySearch(l, newInt);
  if (insertPoint < 0)  insertPoint = -(insertPoint + 1);
  l.add(insertPoint, newInt);
}
l.remove(0);

```

But, are you sure you wanted to discard just 1 item? Or did you mean to insert a set of new items N into sorted list A of size S and keep just the S largest items. In that case, keep track of the min value:

```
int min = l.get(0);
l.ensureCapacity(l.size()+n);

Random rand = new Random();
for (int i=0; i < n; i++) {
  final Integer newInt = Integer.rand.nextInt(1000);
  if (newInt > min) {
    int insertPoint = Collections.binarySearch(l, newInt);
    if (insertPoint < 0)  insertPoint = -(insertPoint + 1);
    l.add(insertPoint, newInt);
  }
}

```

However, if N is large, you may be better off sorting N into an sorted array by itself, discarding the smaller of N(0) or A(0), and then merging the two sorted arrays together [left as an exercise for the reader].

If you end up using an actual array, see [Arrays.binarySearch](http://java.sun.com/j2se/1.4.2/docs/api/java/util/Arrays.html#binarySearch(byte[],%20byte)) and [System.arraycopy](http://java.sun.com/j2se/1.4.2/docs/api/java/lang/System.html#arraycopy(java.lang.Object,%20int,%20java.lang.Object,%20int,%20int)).
If you're working with an ArrayList, you can replace the last number in the array with the new number if the new number is larger before you sort the array.

The Java `Collections.sort` uses merge sort which isn't the most efficient way of sorting in this situation. You want to use a binary search to find the insertion point and then shift all the subsequent numbers along by one.

EDIT: This can all be done with just an array like so:

```
public static int addDiscard(int[] list, int number)
{
    if (number > list[list.length - 1])
    {
        int index = findInsertionIndex(list, number); // use binary search
        for (int i = list.length - 1; i > index; i--)
        {
            list[i] = list[i - 1];
        }
        list[index] = number;
    }
}

```