For a bubble-sorting-based non-Manhattan channel routing (BSNMCR) problem,
Chen's O(k(2)n) optimal algorithm and Yan's O(kn) optimal algorithm have be
en proposed respectively where n is the number of terminals and k is the nu
mber of routing tracks in a channel. For the sorting process of a given vec
tor, these two optimal algorithms consider that a left-swap pass or a right
-swap pass is an overall pass. As the distribution of most of the routing n
ets in a channel has a local property a vector may be divided into several
smaller subvectors, and each subvector can be sorted by a left-swap pass or
a right-swap pass to further optimise the number of tracks in a channel. I
n the paper, based on an optimality-oriented swap-direction selection and a
'divide-and-conquer' technology, a hierarchical BSNMCR (HBSNMCR) problem i
s formulated and an O(hn) optimal algorithm is proposed, where h is the num
ber of routing tracks in a HBSNMCR solution, for h less than or equal to k.