Спасибо! так как многие пользователи сказали, что я должен использовать SortedMap, я уточнил свой вопрос и добавил, что я не могу использовать TreeMap, SortedMap или Collections.Sort или использовать какие-либо решения для сортировки из пакетов JAVA.

т мне нужно реализовать метод, который получает HashMap и сортирует (mergeSort) его значения по ключу(без использования TreeMap, SortedMap или Collections.Sort или использования каких-либо решений для сортировки из пакетов JAVA), моя проблема связана с подстановочными типами ... это моя реализация (которая возвращает ошибки компиляции из-за использования подстановочных знаков)

public HashMap<?, ?> mergeSort(HashMap<?, ?> map) {
        if (map.size() < 1) {
            return map;
        }
        // rounds downwards
        int middle = map.size() / 2;
        int location = 0;

        HashMap<?,?> mapLeft = new HashMap<?, ?>();
        HashMap<?,?> mapRight = new HashMap<?, ?>();
        // splitting map
        for (Iterator<?> keyIter = map.keySet().iterator(); keyIter.hasNext();) {
            if (location < middle) {
                mapLeft.put(keyIter, map.get(keyIter));
            } else {
                mapRight.put(keyIter, map.get(keyIter));
            }
            location++;
        }
        // recursive call
        mapLeft = mergeSort(mapLeft);
        mapRight = mergeSort(mapRight);
        return merge(mapLeft, mapRight);
    }

    public HashMap<?, ?> merge(HashMap<?, ?> mapLeft, HashMap<?, ?> mapRight) {
        HashMap<?, ?> result = new HashMap<?, ?>();
        Iterator<?> keyLeftIter = mapLeft.keySet().iterator();
        Iterator<?> keyRightIter = mapRight.keySet().iterator();
        String keyLeft;
        String keyRight;
        while (keyLeftIter.hasNext()) {
            keyLeft = keyLeftIter.next();
            while (keyRightIter.hasNext()) {
                keyRight = keyRightIter.next();

                if (keyLeft.compareTo(keyRight) < 0) {
                    result.put(keyLeft, mapLeft.get(keyLeft));
                    keyLeft = keyLeftIter.next();
                } else {
                    result.put(keyRight, mapRight.get(keyRight));
                    keyRight = keyRightIter.next();
                }
            }
        }
        return result;
    }

Я ценю вашу помощь!