Sorting a list but the sort order isn't known until runtime

Question

I need to sort a list of strings that I'm reading in but the sorted order of that list is not predetermined (I can't hard code it); I read in the sort order from a source and build a comparator by assigning a numerical value to each entry in a map and then use that to determine the order.

My implementation is pretty simple and straightforward. I don't know if there is any room to optimize this but given that sorting is generally a slow process in itself, I wanted to submit this for code review in case there are in fact any improvements to be made.

The custom comparator will be cached after creation so I won't be building a new one unless required to do so.

import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class RunTest {
   // Runnable test
   public static void main(String[] args) {
      CustomComparator comparator = CustomComparator.fromList(getSortOrder());
      
      List<String> list1 = getTestList();
      
      System.out.println("Test list: \n  " + list1);
      
      Collections.sort(list1, comparator);
      
      System.out.println("Test list (sorted): \n  " + list1);
   }
   
   // Comparator
   public static class CustomComparator implements Comparator<String> {
      private Map<String, Integer> _sortOrder;
      
      public CustomComparator(Map<String, Integer> sortOrder) {
         _sortOrder = sortOrder;
      }
      
      @Override
      public int compare(String l, String r) {
         Integer lvalue = _sortOrder.get(l);
         Integer rvalue = _sortOrder.get(r);
         
         if (lvalue == null || rvalue == null)
            return 0;
         
         if (lvalue < rvalue)
            return -1;
         
         return 1;
      }
      
      public static CustomComparator fromList(List<String> sortOrder) {
         // Map each list item to a comparable integer
         Map<String, Integer> customSortOrder = new HashMap<>();
         
         int i = 0;
         
         for (String s : sortOrder)
            customSortOrder.put(s, i++);
         
         return new CustomComparator(customSortOrder);
      }
   }
   
   // Custom sort order
   public static List<String> getSortOrder() {
      List<String> customSortOrder = new LinkedList<>();
      
      customSortOrder.add("c");
      customSortOrder.add("b");
      customSortOrder.add("a");
      
      return customSortOrder;
   }
   
   // Test list
   public static List<String> getTestList() {
      List<String> randomList = new LinkedList<>();
      
      randomList.add("b");
      randomList.add("a");
      randomList.add("c");
      
      return randomList;
   }
}

Output:

Test list:
  [b, a, c]
Test list (sorted):
  [c, b, a]

Answer 1

This:

     if (lvalue == null || rvalue == null)
        return 0;

doesn't seem very safe. It says that if either of the values does not have a defined order, then don't care about the order, consider them equivalent. This will have the effect of interleaving such items throughout your sorted list.

Technically this fails the requirement of Comparator that

The implementor must also ensure that the relation is transitive

In other words, given some strings a, b and c with ordering indices 1, null and 2, your existing implementation will say that a == b, b == c but a != c - this is non-transitive.

Instead: either throw an exception if there is a value with an undefined order; or choose to default undefined-order values at the beginning or end of the list.

Answer 2

// Runnable test

Javadoc

---

private Map<String, Integer> _sortOrder;

The Java convention does not use underscores to mark fields or members. You'd use the name and then prefix it with this. as needed. Obviously, that's still up to you what you use.

---

      private Map<String, Integer> _sortOrder;
      
      public CustomComparator(Map<String, Integer> sortOrder) {
         _sortOrder = sortOrder;
      }

That allows _sortOrder to be changed from outside the class during runtime, mind you.

---

      public int compare(String l, String r) {
         Integer lvalue = _sortOrder.get(l);
         Integer rvalue = _sortOrder.get(r);

Don't shorten names just because you can! Shortened names only lead to less readable and less maintainable code.

---

         if (lvalue < rvalue)
            return -1;
         
         return 1;

That's incorrect, as far as I can see. If both values match you're returning 1, which is not correct and might lead to an endless loop depending on how the sorting algorithm works. Comparators are supposed to return -1/0/1, but all implementations are compelled/supposed to also accept -n/0/n. SO you can simply subtract both values and return the result:

return lvalue.intValue() - rvalue.intValue();

---

         int i = 0;
         
         for (String s : sortOrder)
            customSortOrder.put(s, i++);

Be aware of Autoboxing.

And again, don't shorten names.

         int value = 0;
         
         for (String item : sortOrder) {
            customSortOrderMap.put(item, Integer.valueOf(value++));
         }

Whether or not you use braces for single lines, is again up to you, it's advised against, though.

---

List<String> customSortOrder = new LinkedList<>();

By default you'd be using an ArrayList, as it is the cheapest implementation when it comes to various operations, that include adding and removing.

---

There's not much else to say about the actual logic, as far as I can see it should work.

Using a Map as intermediate object might not be the nicest choice. Instead, you could allow to modify the Comparator.

public class ValueBasedComparator implements Comparator<String> {
    private Map<String, Integer> values = new HashMap<>();
    
    public ValueBasedComparator addValue(String item, int value) {
        values.put(item, Integer.valueOf(value));
    }
}

Also, I believe you could use generics to make the class generic:

   public static class CustomComparator<ITEM_TYPE> implements Comparator<ITEM_TYPE> {
      private Map<ITEM_TYPE, Integer> _sortOrder;

      @Override
      public int compare(ITEM_TYPE first, ITEM_TYPE second) {

But there might be an edge-case not allowing that, have not tested it.