Sort the elements of $S$ using an external-memory sorting algorithm. This brings together the elements with the same keys. One more scan through this sorted order matches up the red and blue elements. The time for this algorithm is dominated by the time to sort, which can be done using $O((n/B)\log (n/B)/\log (M/B))$ block transfers.