Apparatus and an associated method for facilitating paging of an access terminal that operates in a radio communication system. A paging message is formed that includes a plurality of partial identities that identify access terminals that are to be paged. The partial identities are ordered, such as in ascending order. and additional bits are added to the paging message, associated with, and part of the partial identities, once ordered.