1

i am wondering what sorting algorithm does List.sort() is based upon. When i try to sort the following order and have written a debug statement inside the compareTo method it gives the following output. But the final list is a sorted one from 1,2,3,4,5. Any thoughts please.

Original List

    jobs.add(new OpenSalesOrderWrapper(5,'E','T'));
    jobs.add(new OpenSalesOrderWrapper(2,'B','Q'));
    jobs.add(new OpenSalesOrderWrapper(1,'A','P'));
    jobs.add(new OpenSalesOrderWrapper(4,'D','S'));
    jobs.add(new OpenSalesOrderWrapper(3,'C','R'));

From debug log:

07:57:10.049 (49903000)|USER_DEBUG|[24]|DEBUG|5
07:57:10.049 (49960000)|USER_DEBUG|[24]|DEBUG|5
07:57:10.049 (49999000)|USER_DEBUG|[24]|DEBUG|2
07:57:10.050 (50035000)|USER_DEBUG|[24]|DEBUG|5
07:57:10.050 (50072000)|USER_DEBUG|[24]|DEBUG|2
07:57:10.050 (50107000)|USER_DEBUG|[24]|DEBUG|5
07:57:10.050 (50142000)|USER_DEBUG|[24]|DEBUG|4
07:57:10.050 (50177000)|USER_DEBUG|[24]|DEBUG|2
1
  • Comparable is just an interface. It defines a contract, not the actual functionality (implementation).
    – user6861
    Apr 16, 2014 at 15:28

1 Answer 1

2

I'm assuming the question is really what algorithm does List.sort use (that in turn influences how often the Comparable.compareTo method is called)?

I don't think this is documented but someone with inside knowledge may choose to comment. A reasonable candidate would be Java's Collections.sort that has this to say in its documentation:

The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n log(n) performance. The specified list must be modifiable, but need not be resizable. This implementation dumps the specified list into an array, sorts the array, and iterates over the list resetting each element from the corresponding position in the array. This avoids the n2 log(n) performance that would result from attempting to sort a linked list in place.

1
  • List.sort() used quick sort however non-primitive object like wrapper using Comparable interface uses merge sort.
    – Ayub
    Nov 18, 2019 at 10:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .