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 ?

does these [link1](http://stackoverflow.com/questions/17328077/difference-between-arrays-sort-and-arrays-parallelsort) and [link2](http://java.dzone.com/articles/arrayssort-versus) help you. — Ankur Singhal, Oct 06 '14 at 06:26
@KickButtowski: Are you sure you ran the program correctly. Regardless of the order in which I enter the values, `Orange` is placed first. — Willem Van Onsem, Oct 06 '14 at 06:43

Willem Van Onsem · Accepted Answer · 2014-10-06T07:05:10.500

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.

the outcome must be the same. based on the post, the orange has to be first all the time — Kick Buttowski, Oct 06 '14 at 06:31
All right, but note that for large arrays, items that are "equivalent" (but not the same, for instance a different pointer) can be shuffled... — Willem Van Onsem, Oct 06 '14 at 06:49
The “default” does *not* use `QuickSort` as `QuickSort` is not a stable algorithm and `Collections.sort` is guaranteed to be stable. `QuickSort` might be used where the stability of the sorting is meaningless, e.g. when sorting numbers like `Arrays.sort(int[])` does. It’s worth noting that the comparator of the question does violate the contract of `Comparator` as it doesn’t handle the case that both elements have the name `"orange"` correctly. — Holger, Oct 06 '14 at 11:24

Arrays.parallelSort vs Collections.sort

1 Answers1

Linked