Arrays.parallelSort vs Collections.sort

Question

I was checking a post that wanted to know how to use Comparator and a Orange fruit to be first all the time. From the post toString method was missing so I added to my code

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

The given answer to the post 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 was thinking why not Arrays.parallelSort which I have been told good stuff 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

The link to the post is here

To me sorting is sorting, why different answer form different method ?

Answer 1

If one runs the program in TryJava8, I get the correctly sorted array. I think you probably printed the input (fruits) instead of the output (arrayFruits). This said, you opened an interesting topic, since in general, you are right a sorting algorithm does not guarantee the full order. In general for large arrays, if two elements are equivalent, but not the same (for instance a different pointer to an equivalent record), the algorithms do not guarantee a specific order. This said ties are in general broken differently by different algorithms.

A compare method should satisfy the order relation constraints:

An order relation should be:

• reflexive: every item should be equal to itself (you better return 0 I guess)
• asymmetrical: 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 of the sorting algorithms assume this constraints implicitly (they don't check them) and thus offer a O(n log n) time complexity. If the condition does not hold, depending on the implementation of the algorithm, one obtains different results.

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

A relevant topic: most sorting algorithms are not stable. Say two items are "equal", then it is not guaranteed that if A was placed before A' in the original array, A will be placed before A' in the resulting array.