Q:

Group a list and sort that list by occurrence in java

I have a large list of names (first name and lastname): For example:
{ john a, david x, marry u, john b, david y, john c}
The result should be (grouped by first name, ordered by frequency of the first name, not considering last name.):
john b
john a
john c
david x
david y
marry u

I have a quite large list (30M instances), so I must consider the complexity of the algorithm.

A:

Map<String, Integer> freq = new HashMap<String, Integer>();
for (String s: names):
    first_name = Arrays.asList(s.split()).get(0).toLowerCase()
    int count = freq.containsKey(name) ? freq.get(name) : 0;
    freq.put(name, count + 1);

Arrays.sort(names, new Comparator<String>() {
  public int compare(String s1, String s2) {
    int c = freq.get(Arrays.asList(s1.split()).get(0).toLowerCase()) - Arrays.asList(s2.split()).get(0).toLowerCase();
    return c;
  }
});

Basically make a histogram of the frequency of first name occurrences, then just use it as a custom comparator.
It's just two operations so you're limited by the complexity of the most complex area of the problem and since the histogram generation is linear you're limited by the sort function which I believe is nlogn which is the best you can do with sorting.

