Arrays.parallelSort vs Collections.sort

Question

I was checking a post that would like to know how to use Comparator and Orange Fruit to be the first all the time. There was no post toString method, so I added to my code

 @Override public String toString(){ return fruitName +" " + fruitDesc; } 

This response to the message was

use Collection.sort

 Collections.sort(fruits, new Comparator<Fruit>() { @Override public int compare(Fruit o1, Fruit o2) { if (o1.getFruitName() != null && o1.getFruitName().equalsIgnoreCase("orange")){ return -1; } if (o2.getFruitName() != null && o2.getFruitName().equalsIgnoreCase("orange")){ return 1; } return o1.getFruitName().compareTo(o2.getFruitName()); } }); 

Output :

 Orange Orange description Apple Apple description Banana Banana description Pineapple Pineapple description 

I thought, why not the Arrays.parallelSort , which I was told good things about

read more here

using Arrays.parallelSort code

  Fruit[] arrayFruits = fruits.stream().toArray(Fruit[]::new); Arrays.parallelSort(arrayFruits, (Fruit o1, Fruit o2) -> { if (o1.getFruitName() != null && o1.getFruitName().equalsIgnoreCase("orange")){ return -1; } if (o2.getFruitName() != null && o2.getFruitName().equalsIgnoreCase("orange")){ return 1; } return o1.getFruitName().compareTo(o2.getFruitName()); }); 

Output :

 Pineapple Pineapple description Apple Apple description Orange Orange description Banana Banana description 

Link to the message here

Sorting sorts for me, why are different forms of response different?

Answer 1

If you run the program in TryJava8 , I get a properly sorted array. I think you most likely printed input ( fruits ) instead of output ( arrayFruits ). This suggests that you opened an interesting topic, since in general you are right, the sorting algorithm does not guarantee complete order. In the general case, for large arrays, if two elements are equivalent but not the same (for example, another pointer to an equivalent record), the algorithms do not guarantee a certain order. These relationships are generally violated by different algorithms.

The comparison method must satisfy the constraints of the order relation:

The order relation should be:

• reflexive: each element should be equal to itself (it is better to return 0 , I think)
• asymmetric: if A is less than or equal to B and B is less than or equal to A, A and B are equal.
• transitive: if A is less than or equal to B and B is less than or equal to C, A is less than or equal to C.

Most sorting algorithms imply these restrictions implicitly (they do not test them) and therefore offer O (n log n) time complexity. If the condition is not met, then depending on the implementation of the algorithm, different results are obtained.

Since parallel sorting uses the MergeSort algorithm, and default sorting uses the QuickSort algorithm, the two algorithms have different behavior.

Relevant topic: most sorting algorithms are unstable. Let's say that the two elements are "equal", then it is not guaranteed that if A was placed before A 'in the original array, A would be placed before A' in the resulting array.