There is a basic problem with this approach. To get a benefit from multithreading, you need to give each thread a non-overlapping task compared to the other treads. By synchonizing
on the array
you have made it so only one thread does work at a time, meaning you get all the overhead of threads with none of the benefit.
Think of ways to partition the task so that threads work in parallel. For example, after the first pass, all the item with a 1 high bit will be in one part of the array, and those with a zero high-bit will be in the other. You could have one thread work on each part of the array without synchronizing.
Note that your runnable
has to completely change so that it does one pass at a specified subset of the array then spawns threads for the next pass.