Random iteration over an array using divide and conquer
Bug?


    private final ThreadLocalRandom random = ThreadLocalRandom.current();



This doesn't look right.  What happens if your current thread copies your object and spawns a new thread?  It will copy the current random instance.  

When you use it 


            final int randomIndex = random.nextInt(lowerBound, upperBound);



You should instead say 

            final int randomIndex = ThreadLocalRandom.current().nextInt(lowerBound, upperBound);


That way, even if your object exists in multiple threads, each one will access a separate instance of ThreadLocalRandom.  

Your current implementation may return the same random result multiple times, which would give the "non-random" appearance that you're seeing.  

Note that if you are using an old version of Java, there was apparently a bug that could cause this to happen even when called correctly.