Now we are ready to begin the merging phase. As mentioned above, we
merge the p subimages into larger and larger image sections with
consistent labelings. There will be 
iterations since we cut
the number of uncombined subimages in half during each iteration.
Unlike previous connected components algorithms, we use a technique
which identifies processors as group managers or clients
during each phase. The group managers have the task of organizing the
retrieval of boundary data, performing the merge, and creating the
list of label changes. Once the group managers broadcast these changes
to their respective clients, all processors must use the information
to update their tile hooks, data structures which point to
connected components on local tile borders. See
Figure 5 for an illustration of the tile hook data
structure in which three tile hooks contain the information needed to
update the border pixels. The clients assist the group managers by
participating in the coalescing of data during each merge phase.
Finally, the complete relabeling is performed at the very end using
information from the tile hooks.
Without loss of generality, we first perform a horizontal merge along
every other vertical border, then a vertical merge along every other
horizontal border, alternating orientation until we have merged all
the tiles into one consistent labeling. We merge vertical borders
exactly 
times, where w is the number of columns in the
logical processor grid. Similarly, we merge horizontal borders
exactly 
times, where v is the number of rows in the logical
processor grid.
The merging algorithm for a horizontal merge is similar to that of a vertical merge. Most of the code is identical, except for substituting ``up'' for ``left'' and ``down'' for ``right.'' However, one nontrivial change relates to identifying during each iteration which processors will be group managers and which will be clients, concepts defined precisely in the following section.