Return to Answer

Just a few minor things that @rolfl (probably intentionally) left out.

Just a few minor things on top of @rolfl's answer.

Unit testing

Code organization

Why pass a Map to the void method groupAnagrams? Why not pass only the input parameters and make it return a Collection (or List) of the results?

One big reason to do this is that callers of the groupAnagrams shouldn't need a Map at all. The fact that groupAnagrams uses a Map in its algorithm is just an implementation detail. The caller really needs only a collection (or list) of the results.

Unit testing

User interface types when possible

Do this way everywhere, for example in the groupAnagrams method too.

Use interface types when possible

Do this way everywhere, for example in the groupAnagrams method too.

Unit testing

To verify that your algorithm actually works, it's good to have unit tests.

@Test
public void test_mother_mothre_dad_add_gift_gender() {
    Map<Integer, List<String>> map = new HashMap<>();
    AnagramSort.groupAnagrams(new String[]{"mother", "mothre", "dad", "add", "gift", "gender"}, map);
    assertEquals("[[gender], [dad, add], [gift], [mother, mothre]]", map.values().toString());
}

Once you have this (and hopefully more) test cases, you can refactor your algorithm like @rolfl suggested, and when your done you can simply re-run the tests with one simple click, and you'll know immediately if the implementation works or not.