Why does seeding this Random object lead to unexpected Comparator behavior?

Question

I'm a student teaching myself about Comparators and I came across odd behavior that I'm having trouble understanding. I'm attempting to shuffle an array using Arrays.sort and a Random object, however when I seed the Random object the shuffle either reverses the array or does nothing. Not seeding the Random object leads to it being shuffled as expected.

No seed:

Integer[] integers = new Integer[]{1, 2, 3, 4, 5, 6};
Arrays.sort(integers, new Comparator<T>() {
        @Override
        public int compare(T o1, T o2) {
            return new Random().nextInt();
        }
    });

>>> [4, 3, 5, 2, 1, 6] 

Seed:

Integer[] integers = new Integer[]{1, 2, 3, 4, 5, 6};
Arrays.sort(integers, new Comparator<T>() {
        @Override
        public int compare(T o1, T o2) {
            return new Random(System.currentTimeMillis()).nextInt();
        }
    });

>>> [1, 2, 3, 4, 5, 6] or [6, 5, 4, 3, 2, 1]

Could someone help me understand this behavior?

I do understand this is terrible code. These are just toy examples to help me get familiar with the mechanics of Comparators. I'm more interested in the resulting behavior regardless.

Answer 1

Seeding controls the random number stream you generate. If you seed with the same seed, you'll get the same sequence every time. You're seeding here with the same number each time (because it won't take even 1ms to do the sort), so the nextInt() will always return the same value. Thus it will always return the same sort. Since your data is sorted coming in, that causes it to stay in the same order.

If you want to seed correctly, create the Random object once, and call it rather than recreating with the same seed each time.

Answer 2

Much of your Random objects created will get the same seed since the code runs fast.

For example, you could throw in a brief Thread.sleep(10) in your Comparator. Or you could run:

  for (int i = 0; i < 7; i++) {
     System.out.println("" + new Random(System.currentTimeMillis()).nextInt());
  }

You do understand why this is terrible code, right? You would only create one Random object once, and then use the same one in your Comparator, right?

Answer 3

Even if you use only a single Random object you will still get unexpected behavior with a random Comparator. From the documentation from Comparator.

The implementor must ensure that sgn(compare(x, y)) == -sgn(compare(y, x)) for all x and y.

By not following that implementation requirement you will get undefined behavior. You can see a visualization of what the resulting shuffles look like here: http://bost.ocks.org/mike/shuffle/compare.html

(Note: the shuffles there are using Javascript not Java, but the issue applies to Java as well.)