Compare [0, 1] [2, 3] [4, 5] ... in parallel and swap if necessary, compare/swap [1, 2] [3, 4] [5, 6] ... in parallel, then go back and forth until no more swaps are made - second element in pair is always greater/less than the first.

That does suggest that the theoretical ideal number of threads is n / 2 ignoring cores, though you'll also want to consider things like cache line size, cache coherency, and actual problem size so it's probably less.

At the end of the day, the important thing would be to actually benchmark your attempts and seeing how it scales with processors/problem size and checking the isoefficiency.

I think it was a bad question.