Двойная сортировка в Map

        int index = mapDistance.size();
        CompareMapValue[] compareMapValues = new CompareMapValue[index];
        index = 0;
        for (HashMap.Entry<List<String>, String> entry : mapDistance.entrySet()) {
            compareMapValues[index++] = new CompareMapValue(entry.getKey(), Integer.parseInt(entry.getValue()));
        }
        Arrays.sort(compareMapValues);
        int keyNum = 0;
        for (CompareMapValue cmv : compareMapValues) {
            List<String> list = new ArrayList<>();
            list.add(String.valueOf(cmv.list));
            list.add(String.valueOf(cmv.i));
            mapDistanceSort.put(list, keyNum);
           // mapDistanceSort2.put(cmv.list, cmv.i);
            keyNum++;
        }

public class CompareMapValue implements Comparable {
public List<String> list;
public Integer i;
public CompareMapValue(List<String> list, Integer i) {
    this.list = list;
    this.i = i;
}
public int compareTo(Object o) {
    if (o instanceof CompareMapValue) {
        final int diff = i.intValue() - ((CompareMapValue) o).i.intValue();
        return diff < 0 ? -1 : (diff > 0 ? 1 : 0);
    } else {
        return 0;
    }
}
}

[[Иванов, Иван, 0], 25]
[[Сидоров, Коля, 1], 15]
[[Иванов, Иван, 1], 25]
[[Кузним, Кузя, 0], 45]
[[Савелов, Сава, 1], 74]

[[Сидоров, Коля, 1], 15]
[[Иванов, Иван, 0], 25]
[[Иванов, Иван, 1], 25]
[[Кузним, Кузя, 0], 45]
[[Савелов, Сава, 1], 74]

[[Сидоров, Коля, 1], 15]
[[Иванов, Иван, 1], 25]
[[Савелов, Сава, 1], 74]
[[Иванов, Иван, 0], 25]
[[Кузним, Кузя, 0], 45]

   Map<List<String>, Integer> n = new TreeMap<List<String>, Integer>(new Comparator<List<String>>() {
            @Override
            public int compare(List<String> o1, List<String> o2) {
                String[] o3 = o1.get(0).split(", ");
                String[] o4 = o2.get(0).split(", ");
                return Integer.parseInt(o4[2].replace("]", "").trim()) - Integer.parseInt(o3[2].replace("]", "").trim());
            }
        });
        n.putAll(mapDistanceSort);
        System.out.println(n);

Можно воспользоваться возможностями Java 8 Stream API и решить довольно просто:

Map<List<String>, Integer> sortedMap = map.entrySet().stream()
    .sorted(
        Comparator.<Map.Entry<List<String>, Integer>, String>
            comparing(e -> e.getKey().get(2)).reversed()
            .thenComparingInt(Map.Entry::getValue)
    ).collect(
        Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue)
    );

Сначала выполняем сортировку в обратном порядке по третьему значению из списка: comparing(e -> e.getKey().get(2)).reversed(), а затем - сортировку по значению: thenComparingInt(Map.Entry::getValue).

PS: Здесь результат снова собирается в Map с помощью collect, однако после этого порядок снова не гарантируется. Лучше использовать непосредственно стрим, например, направив его на вывод:

map.entrySet().stream()
    .sorted(
        Comparator.<Map.Entry<List<String>, Integer>, String>
            comparing(e -> e.getKey().get(2)).reversed()
            .thenComparingInt(Map.Entry::getValue)
    ).forEach(System.out::println);

Вывод:

[Сидоров, Коля, 1]=15
[Иванов, Иван, 1]=25
[Савелов, Сава, 1]=74
[Иванов, Иван, 0]=25
[Кузним, Кузя, 0]=45

Ваш подход некорректный. Вы передаете лист в качестве ключа, отсюда вы получите огромное количество проблем. Фактически этот лист еще и типизирован Object либо в крайнем случае String, хотя в рельности там и строки и цифры. Мало того, очень сложно контролировать в какоми именно элементе листа что лежит. При этом не стоит забывать, что любая Map работает с хешкодом, а в Вашем случае это хешкод листа Object и такой же equels. Следующая проблема в том, что у Map всего 3 реализации , из которой HashMap вообще не гарантирует упорядоченности элементов, т.е. в ее пределах вы вообще ничего не можете отсортировать. LinkedHashMap хранит элементы в том порядке, в котором они туда отправились. Остатся только TreeMap, это как раз сортированная коллекция и работает она , как и все сортировки в коллекциях , на основе компоратора. Поэтому , если вам действительно нужен Map в этом случае, рекомендовал бы пользоваться последней, а ваших людей затолкнуть в специальный класс, где вы сможете контролировать вышеуказанные equels, hashCode, кроме того, сами переопределите метод compare для сортировки, а еще четко будете знать, какая переменная какое поле хранит. Но лично я рекомендовал бы вам в данном случае вообще не использовать Map. Берите List либо Set для уникальных объектов. В последнем тоже есть TreeSet, работающий по тому же принципу, что и TreeMap, а для любого листа есть Collections.sort. Ваше значение в map я так понимаю, что это возраст, нужно сделать еще одним полем класса и всех делов. И тогда для любого листа вы можете написать неограниченное количество компараторов и пользоваться любым по выбору, сортируя эти данные как вам угодно. Код выглядит примерно так.

public class Person implements Comparable<Object> {    
    //for testing only
    public static void main(String[] args) {
        Map <Person,Integer> map = new TreeMap <> ();
        map.put(new Person("Иванов", "Иван", 0), 25);
        map.put(new Person("Сидоров", "Коля", 3), 15);
        map.put(new Person("Петров", "Петр", 1), 25);
        map.put(new Person("Кузним", "Кузя", 2), 45);
        map.put(new Person("Савелов", "Сава", 0), 74);
        System.out.println(map);
    }
    private String surname;
    private String name;
    private int priority;    
    public Person() {
    }
    public Person(String surname, String name, int priority) {
        this.surname = surname;
        this.name = name;
        this.priority = priority;
    }
    public String getSurname() {
        return surname;
    }
    public void setSurname(String surname) {
        this.surname = surname;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public int getPriority() {
        return priority;
    }
    public void setPriority(int priority) {
        this.priority = priority;
    }
    @Override
    public int hashCode() {
        int hash = 3;
        hash = 67 * hash + Objects.hashCode(this.surname);
        hash = 67 * hash + Objects.hashCode(this.name);
        hash = 67 * hash + this.priority;
        return hash;
    }
    @Override
    public boolean equals(Object obj) {
        if (this == obj) {
            return true;
        }
        if (obj == null) {
            return false;
        }
        if (getClass() != obj.getClass()) {
            return false;
        }
        final Person other = (Person) obj;
        if (this.priority != other.priority) {
            return false;
        }
        if (!Objects.equals(this.surname, other.surname)) {
            return false;
        }
        if (!Objects.equals(this.name, other.name)) {
            return false;
        }
        return true;
    }
    @Override
    public String toString() {
        return "Person{" + "surname=" + surname + ", name=" + name + ", priority=" + priority + '}';
    }
    @Override
    public int compareTo(Object o) {   
        try {
            Person p = (Person) o;
            if (p.getPriority() == this.priority) {
                return p.hashCode()-this.hashCode();
            }
            if (p.getPriority() < this.priority) return -1;
            else return 1;
        } catch (NullPointerException | ClassCastException e) {
            return 1;
        }
    }
}

Если все таки хотите костыль , то можно так

public static Map sortMap(Map<List<String>, Integer> mapDistanceSort) {
    Map<List<String>, Integer> sortedMap = new LinkedHashMap<>(mapDistanceSort.size());
    mapDistanceSort.forEach((k,v)->{if ("0".equals(k.get(2))) sortedMap.put(k, v);});
    mapDistanceSort.forEach((k,v)->{if ("1".equals(k.get(2))) sortedMap.put(k, v);});
    return sortedMap;
}

Вообще у вас не совсем правильная архитектура, если вам нужно сортировать по приоритету и значению, значит это ключи, соотвественно Map'a (или временная Map'a) должна содержать объектыMap, где key это объект c полями priority и value, а Value со всеми остальными (естественно имена типов должны быть более подходящими). Тогда для сортировки можно использовать обычныйTreeMap`.