Coming into this late but there are three items which should be asked explicitly and were only implied in various replies along the way. First: is the data in the array mutable? Second: how variable is the execution time of the work, short on some, longer on others, 2x, 3x, more variation? What amount of work are we talking about? These three questions should preface any discussion of multi-threading since there are very important implications of each.
Taking the first item. If the data is mutable, then make it immutable. That solves the issues of alignment and cache line false sharing in the input side. So, in the first response suggesting making copies, don't do that, just all read from the initial array but 'store' the results to a second array. When everything is done, the results are in the second array, if they happen to be pointers, just swap the pointers and away you go. False sharing in the 'output' array is still possible but with partitioning of any significant amount of work, the threads should never be looking at data in close proximity so it should never show up as a problem. I.e. thread 1 would have to be nearly done with it's work before it got near work thread 2 is looking at, unless thread 2 was REALLY slow, it should have moved out of the area of contention so there is no overlap.
Second item: variable execution time can destroy performance in any partitioning scheme. If one thread gets unlucky working on heavier work items, the other threads will be stuck waiting till that one gets done. Most partitioning schemes are meant for nearly fixed cost computations where no one thread gets stuck doing unexpectedly large amounts of work.
Third item: as suggested, you should only do this on significantly large amounts of data. Something I did not see mentioned at all is that threads don't wake up from mutex/semaphore/etc immediately, so right off the top you loose a significant amount of performance due to slow wakeup on the worker threads. Unless you have the threads in a busy wait andthe work is significant, you may never see a benefit.
Hope I didn't restate too much, but I didn't see much of this asked specifically.