Consider that we have array $A$ of integers with length $n$. Each element of this array is tagged either with "blue" or "red". We know blue elements are sorted, and red elements are sorted; however, actually it does not mean the whole array is sorted. For example, maybe $A=[3,1,4,2,5,6]$ where 3 and 4 and 5 are red and the others are blue.
Give a fast parallel algorithm to sort A. Actually, the number of processors is $O(n/ log n)$ and the time complexity should be $O(log n)$. It is part of the section 14.2.6 of the Goodrich algorithm book about findinng the diameter of a convex polygon in parallel.
If someone can tell me how to seperate the array to two different arrays, one with red elements with preserving order, and the other one for blue elements with preserving order, I think I cann do the rest. Please notice that the sum of the size of those two arrays should be $n$.