Here is a little class I wrote for a similar problem. Once you have the
set of keys, you can sort it using a Comparator that orders based on the
associated count. You will need to modify it to remove the generics to
use with 1.4. I'd be interested in hearing whether it is faster or
slower than your current solution.

/*
 * Created on Aug 14, 2004
 */
package utilities;

import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/**
 * Utility class for counting instances of equal objects.
 */
public class Counter {

  private Map<Object,Count> data = new HashMap<Object,Count>();

  /**
   * Increment by one the count associated with a specified
   * key.
   * @param key
   */
  public void increment(Object key) {
    Count count = data.get(key);
    if (count == null) {
      count = new Count();
      data.put(key, count);
    }
    count.increment();
  }

  /**
   * Get the count associated with a specified key.
   * @param key The key whose count is required.
   * @return The number of times increment has been called with
   * a key equal to this one.
   */
  public int get(Object key) {
    Count count = data.get(key);
    if (count == null) {
      return 0;
    } else {
      return count.get();
    }
  }

  /**
   * Get number of unique counted objects
   *
   * @return Number of key objects for which increment
   * has been called. Equal objects are only counted once.
   */
  public int size() {
    return data.size();
  }

  /**
   * Get all the unique counted objects
   * @return A set containing a refence to the counted objects.
   */
  public Set getKeys() {
    return Collections.unmodifiableSet(data.keySet());
  }

  private static class Count {
    private int val = 0;

    private void increment() {
      val++;
    }

    private int get() {
      return val;
    }
  }

}

 So you want

sort | uniq -c

 You might use something like

class NumericMapUtils
{ public static <D> void addTo /* autovivificate the value to 0 */
 ( final java.util.Map<D,java.lang.Integer> map, final D d, final int i )
 { map.put( d, i +( map.containsKey( d )? map.get( d ): 0 )); }}

 and a sorted map

java.util.TreeMap<java.lang.String,java.lang.Integer> map;

 then add each text like

NumericMapUtils.addTo<java.lang.String>( map, "Apple",  1 );
NumericMapUtils.addTo<java.lang.String>( map, "Orange", 1 );
NumericMapUtils.addTo<java.lang.String>( map, "Apple",  1 );
NumericMapUtils.addTo<java.lang.String>( map, "Apple",  1 );

 Then iterate: »for( final java.lang.String key: map.keySet() )«

Now I am confused.

[....]

Neither of the suggested solutions would meet this condition. Or would
they? What am I missing?

You need a collection of (word, frequency). When building the
collection, you want it searchable by the word. When reporting, you
need it sorted by frequency. One way is to sort the collection after
the scan. Would that be worse then maintaining two collections during
scan? I don't know...

If I remember right, the K&R C Programming Language book has a sample
code for word frequency.