0

I found this code snippet on codeforces.

 public static int[] sort(int[] a) {
        a = shuffle(a, new SplittableRandom());
        Arrays.sort(a);
        return a;
    }

Is this a better way to sort an array rather than using just Arrays.sort(a). Why or Why not?

sschrass
  • 7,014
  • 6
  • 43
  • 62
P.Gupta
  • 485
  • 4
  • 18
  • 1
    Better to define better first... – xingbin Apr 07 '18 at 10:21
  • 3
    How could something shuffling an array randomly and then sorting it be faster or better than just sorting it? – JB Nizet Apr 07 '18 at 10:21
  • 2
    @lexicore sure, that's my point. But the OP doesn't ask if **there** is a better way. The question is: *is **this** a better way*. – JB Nizet Apr 07 '18 at 10:24
  • Are you asking if "shuffle-then-`Arrays.sort`" is "better" that simply `Arrays.sort`? Or if there's anything "better" than `Arrays.sort`? (Whatever "better" means.) – lexicore Apr 07 '18 at 10:28
  • 1
    @JBNizet On a second thought, it seems to me the question is not as trivial as it seems. `Arrays.sort` uses `DualPivotQuicksort` which (I think) is not randomized. So shuffling the array might even make some sense. – lexicore Apr 07 '18 at 10:35
  • Possible duplicate: https://stackoverflow.com/questions/27645471/how-does-random-shuffling-in-quick-sort-help-in-increasing-the-efficiency-of-the – lexicore Apr 07 '18 at 10:41

1 Answers1

0

It's because Arrays.sort() uses Quicksort (Dual-Pivot Quicksort, to be more precise), which can have a complexity of O(n^2) (worst case complexity), instead of O(n log(n)), when the array has small or big values on the first/last position. In other words, Quicksort has the best efficiency when the order of the elements is completely random.

You can find a more detailed explanation here.

Teodor Afrim
  • 5
  • 3