Dynamic return type based on input argument type

I’m trying to write a small function that takes two lists and sorts one based on the elements of the other. So something like:

List<Integer> keys = Arrays.asList(3, 5, 2, 4, 1);
List<String> valuesToSort = Arrays.asList("A", "B", "C", "D", "E");

List<String> sortedValues = sort(keys, valuesToSort);

would result in a sorted list [E, C, A, D, B].

However, valuesToSort might be a list of something different, like integers, floats or other lists. Ideally, I would want my program to take any list I throw at it, sort it according to keys, and then return a list of the same type as the input. How would I do that? If the type of values were fixed, the sorting itself would be straightforward, like for example

public List<String> sort(List<Integer> keys, List<String> values){
    Multimap<Integer, String>> multiMap = LinkedListMultimap.create();
    for (int i = 0; i < keys.size(); i++) {
        multiMap.put(keys.get(i), values.get(i));
    }
    List<String>> sortedValues = Lists.newArrayList();
    for (Integer key : Ordering.natural().sortedCopy(multiMap.keys())) {
        for (String value : multiMap.get(key)) {
            sortedValues.add(value);
        }
    }
return sortedValues;
}

but this only works if values is a list of the expected type.

Answer

You can use Generics for this as follow:

public List<T> sort(List<Integer> keys, List<T> values){
    Multimap<Integer, T>> multiMap = LinkedListMultimap.create();
    for (int i = 0; i < keys.size(); i++) {
        multiMap.put(keys.get(i), values.get(i));
    }
    List<T> sortedValues = Lists.newArrayList();
    for (Integer key : Ordering.natural().sortedCopy(multiMap.keys())) {
        for (T value : multiMap.get(key)) {
            sortedValues.add(value);
        }
    }
    return sortedValues;
}

Now, when you pass list of strings, the generic T would be considered as String. When you pass list of integers, T would become Integer. This will happen at runtime.