I'm guessing this is homework or an uni assignment or such, because no sane person would request you use bubble sort with threads for something real. Bubble sort is the probably most embarrassingly poor sort algorithm in existence, and throwing "multithreading" at a poor algorithm to make it faster (when better single-threaded algorithms exist) is a poor approach.

However, after thinking about it for a minute just now, I figured that it is actually a quite interesting exercise. And, in fact, not so silly at all.

Bubblesort is, surprisingly, actually a quite good fit for multithreading (not perfect, but quite good!). Bubblesort runs several passes over the complete set of data, only ever examining two adjacent values and swapping them if they're not in order. It's a O(N²) average algorithm. Obviously, smaller pieces of data will therefore be considerably faster (using 4 threads on partitions 1/4 the size reduces the number of operations to 1/16). That means you're doing better than Amdahl's law!

You can trivially partition the set into N pieces and run the N pieces in N threads, in parallel. You can then, after syncing at a barrier, merge the partitions by taking the i-th element of every partition, which gives an "almost sorted" dataset. On a perfectly evenly distributed dataset, it would be sorted, not "almost sorted", but of course you want it to work for any data. A final pass of bubblesort over the whole set makes the "almost sorted" set sorted. Sorting "almost sorted" data with bubblesort is very efficient, usually a single pass.

Now, if you want to do it more elegantly than the trivial approach of N threads sorting N pieces, you can for example have N threads sort 4*N pieces, using a worker queue. This has a little added complexity, but considers that not all sub-partitions will take the same number of iterations. Thus, you avoid CPU cores going idle while they wait for the slowest one to finish.

I'm guessing this is homework or an uni assignment or such, because no sane person would request you use bubble sort with threads for something real. Bubble sort is the probably most embarrassingly poor sort algorithm in existence, and throwing "multithreading" at a poor algorithm to make it faster (when better single-threaded algorithms exist) is a poor approach.

However, after thinking about it for a minute just now, I figured that it is actually a quite interesting exercise. And, in fact, not so silly at all.

Bubblesort is, surprisingly, actually a quite good fit for multithreading (not perfect, but quite good!). Bubblesort runs several passes over the complete set of data, only ever examining two adjacent values and swapping them if they're not in order. It's a O(N²) average algorithm. Obviously, smaller pieces of data will therefore be considerably faster (using 4 threads on partitions 1/4 the size reduces the number of operations to 1/16). That means you're doing better than Amdahl's law!

You can trivially partition the set into N pieces and run the N pieces in N threads, in parallel. You can then, after syncing at a barrier, merge the partitions by taking the i-th element of every partition, which gives an "almost sorted" dataset. On a perfectly evenly distributed dataset, it would be sorted, not "almost sorted", but of course you want it to work for any data. A final pass of bubblesort over the whole set makes the "almost sorted" set sorted. Sorting "almost sorted" data with bubblesort is very efficient, usually a single pass.