Your data needs to be sorted, but you don’t want to stop and sort it periodically.

Not everything that requires order requires an explicit sort operation. Just keep the data sorted at all times.

You can avoid the overhead and elapsed time of an explicit sorting operation by ensuring that the data is in the correct order at all times. You can do this manually or, in Java 2, by using a TreeSet or a TreeMap . First, some code from a call tracking program that I first wrote on JDK 1.0 to keep track of people I had extended contact with. Far less functional than a Rolodex, my CallTrak program maintained a list of people sorted by last name and first name. For each person it also had the city, phone number, and email address. Here is a portion of the code that was the event handler for the New User push button:

/** The list of User objects. */
Vector usrList = new Vector(  );
/** The scrolling list */
java.awt.List visList = new List(  );
/** Add one (new) Candidate to the lists */
protected void add(Candidate c) {
    String n = c.lastname;
    int i;
    for (i=0; i<usrList.size(  ); i++)
        if (n.compareTo(((Candidate)(usrList.elementAt(i))).lastname) <= 0)
            break;
        visList.add(c.getName(  ), i);
        usrList.insertElementAt(c, i);
        visList.select(i);      // ensure current
    }

This code uses the String class compareTo(String) routine. This has the same name and signature as the compareTo(Object) in Comparable, but was added to the String class in JDK 1.1, before the Comparable interface was defined.

If I were writing this code today, on Java 2, I would probably use a TreeSet (which keeps objects in order) or a TreeMap (which keeps the keys in order, and maps from keys to values; the keys would be the name and the values would be the Candidate objects). These both insert the objects into a tree in the correct order, so an Iterator that traverses the tree always returns the objects in sorted order. In addition, they have methods such as headSet( ) and headMap( ), which give a new object of the same class containing objects lexically before a given value. The tailSet( ) and tailMap( ) methods return objects greater than a given value, and subSet( ) and subMap( ) return a range. The first( ) and last( ) methods retrieve the obvious components from the collection. The following program uses a TreeSet to sort some names:

// TreeSetDemo.java
/* A TreeSet keeps objects in sorted order. We use a
 * Comparator published by String for case-insensitive
 * sorting order.
 */
TreeSet tm = new TreeSet(String.CASE_INSENSITIVE_ORDER);
tm.add("Gosling");
tm.add("da Vinci");
tm.add("van Gogh");
tm.add("Java To Go");
tm.add("Vanguard");
tm.add("Darwin");
tm.add("Darwin");    // TreeSet is Set, ignores duplicate. See Section 7.12.

// Since it is sorted we can ask for various subsets
System.out.println("Lowest (alphabetically) is " + tm.first(  ));
// Print how many elements are greater than "k"
System.out.println(tm.tailSet("k").toArray(  ).length + 
    " elements higher than "k"");

// Print the whole list in sorted order
System.out.println("Sorted list:");
java.util.Iterator t = tm.iterator(  );
while (t.hasNext(  ))
    System.out.println(t.next(  ));

One last point to note is that if you have a Hashtable or HashMap (and Java 2), you can convert it to a TreeMap , and therefore get it sorted, just by passing it to the TreeMap constructor:

TreeMap sorted = new TreeMap(unsortedHashMap);