Sort java HashMap by values using O(n log n) complexity

Question

I know this question has been asked and answered many times. But almost all of the solutions have a computational complexity of O(n^2).

I am looking for a solution with O(n log n) complexity. Can someone please suggest?

Thanks heaps, Chaitanya

Possible duplicate http://stackoverflow.com/questions/109383/how-to-sort-a-mapkey-value-on-the-values-in-java And that has an answer with `O(n)` complexity — noMAD, May 22 '12 at 23:24
Why not use a TreeMap? EDIT - that's also what's suggested in the question linked by noMAD. — rob, May 22 '12 at 23:27
The answer to the question linked by @noMAD has several critical flaws (as suggested in the comments to that answer). In particular, if several keys map to the same value, things will _break._ If you call `map.get(key)` on a key not in the source map, you'll get almost unpredictable exceptions with confusing stack traces. And how is that solution `O(n)`? — Louis Wasserman, May 22 '12 at 23:31
Also, if the backing map changes values, the `TreeMap` can become corrupted, so entries that appear in `entrySet` won't appear when you call `get`. Ugh. I have seen far too many people try that `TreeMap` approach only to get hurt by it later. Please, avoid it. — Louis Wasserman, May 22 '12 at 23:40
What do you mean 'almost all of the solutions have a computational complexity of O(n^2)'? All the most common sorting algorithms have complexity O(N log(N)). Unless the only solution you have heard of is bubble sort, which you should forget about as soon as you've completed the CS101 assignment. — user207421, May 23 '12 at 00:22
Well, let's be fair: insertion sort is a common component of even modern sorting algorithms, when `n` gets small enough, and it's quadratic. But I can't imagine how it would be any more applicable here than O(n lg n) algorithms. — Louis Wasserman, May 25 '12 at 13:40

score 6 · Accepted Answer · answered May 22 '12 at 23:19

Copy the entries to a List, sort the List by values; copy back into a LinkedHashMap. I don't think a significantly better solution is even possible.

List<Entry<K, V>> entries = new ArrayList<Entry<K, V>>(map.entrySet());
Collections.sort(entries, new Comparator<Entry<K, V>>() {
  public int compare(Entry<K, V> left, Entry<K, V> right) {
    return left.getValue().compareTo(right.getValue());
  }
}
Map<K, V> sortedMap = new LinkedHashMap<K, V>(entries.size());
for (Entry<K, V> entry : entries) {
  sortedMap.put(entry.getKey(), entry.getValue());
}

Sort java HashMap by values using O(n log n) complexity

1 Answers1