What is the best algorithm to sort a list on the basis of two criteria?

Question

I have a list which I need to sort based on two criteria. The first criterion is a Boolean, let's say isBig. The second one is a Long, which represents a timestamp.

I need to order the elements of the list in this way: before the isBig = true, and then the isBig = false. Within these groups, the single elements should be ordered descending on the basis of their timestamp.

Basically, I expect the result to be something like this:

isBig - 2015/10/29
isBig - 2015/10/28
isBig - 2015/10/27
!isBig - 2015/10/30
!isBig - 2015/10/27
!isBig - 2015/10/26

Let's say the object is this:

public class Item {
    Boolean isBig;
    Long timestamp;
    // ...
}

and the list is just List<Item> list.

I figured out that one method would be make three for-cycles: the first to make up the two groups: isBig and !isBig. The second and the third for sorting the elements within them. Finally I merge the two lists.

Is there a more efficient algorithm for sorting lists on the basis of two criteria?

Answer 1

You can sort the list directly using a custom comparison method which checks both criteria.

Use the Collections.sort method and pass a custom comparator with the method compare overriden to:

 int compare(Item o1, Item o2) {
   if (o1.isBig && !o2.isBig)
     return -1;
   if (!o1.isBig && o2.isBig)
     return 1;
   if (o1.timestamp < o2.timestamp)
     return -1;
   if (o1.timestamp > o2.timestamp)
     return 1;
   return 0;
 }

If you are obsessed with performance you could possibly speed it up by a few percents with a more sophisticated approach, but for a list of a few hundred elements the gains would be negligible.

An optimized comparison method:

int compare(Item o1, Item o2) {
   int bigness = (o2.isBig ? 2 : 0) - (o1.isBig ? 2 : 0);
   long diff = o1.timestamp - o2.timestamp;
   return bigness + (int) Long.signum(diff);
}

It features no conditional branches what means it will probably be faster than the naive version above.

That's probably everything that can be done for performance. If we knew something more about your data (for instance there are always more big object than small ones, or all the timestamps are unique, or all the timestamps are from a certain narrow range etc) we could probably propose some better solution. However, when we assume that your data is arbitrary and has no specific pattern than the very best solution is to use a standard sort utility like I've shown above.

Splitting the list into two sublists and sorting them separately will definitely be slower. Actually the sorting algorithm will most probably divide the data into two groups and then recursively into four groups, and so on. However, the division won't follow the isBig criterion. If you want to learn more, read how quick sort or merge sort work.