+without indexing of arrays.
+
+We will keep a~list of the per-vertex structures and we will use it to establish the order of~vertices.
+Each such structure will be endowed with a~pointer to the head of the list of items in
+the corresponding bucket. Inserting an~edge to a~bucket can be then done in constant time
+and scanning the contents of all~$n$ buckets takes $\O(n+m)$ time.
+
+At last, we must not forget that while it was easy to \df{normalize} the pairs on the RAM
+by putting the smaller identifier first, this fails on the PM because we can directly
+compare the identifiers only for equality. We can work around this again by bucket-sorting:
+we sort the multiset $\{ (x,i) \mid \hbox{$x$~occurs in the $i$-th pair} \}$ on~$x$.
+Then we reset all pairs and re-insert the values back in their increasing order.
+This also takes $\O(n+m)$.
+
+\paran{Tree isomorphism}%
+Another nice example of pointer-based radix sorting is a~Pointer Machine algorithm for
+deciding whether two rooted trees are isomorphic. Let us assume for a~moment that
+the outdegree of each vertex is at most a~fixed constant~$k$. We begin by sorting the subtrees
+of both trees by their depth. This can be accomplished by running depth-first search to calculate
+the depths and bucket-sorting them with $n$~buckets afterwards.
+
+Then we proceed from depth~0 to the maximum depth and for each depth we identify
+the isomorphism equivalence classes of the particular subtrees. We will assign
+unique \df{codes} (identifiers) to all such classes; at most~$n+1$ of them are needed as there are
+$n+1$~subtrees in the tree (including the empty subtree). As the PM does not
+have numbers as an~elementary type, we create a~``\df{yardstick}'' ---a~list
+of $n+1$~distinct items--- and we use pointers to these ``ticks'' as identifiers.
+When we are done, isomorphism of the whole trees can be decided by comparing the
+codes assigned to their roots.
+
+Suppose that classes of depths $0,\ldots,d-1$ are already computed and we want
+to identify those of depth~$d$. We will denote their count of~$n_d$. We take
+a~root of every such tree and label it with an~ordered $k$-tuple of codes
+of its subtrees; when it has less than $k$ sons, we pad the tuple with empty
+subtrees. Tuples corresponding to isomorphic subtrees are identical up to
+reordering of elements. We therefore sort the codes inside each tuple and then
+sort the tuples, which brings the equivalent tuples together.
+
+The first sort (inside the tuples) would be easy on the RAM, but on the PM we
+have to use the normalization trick mentioned above. The second sort is
+a~straightforward $k$-pass bucket sort.
+
+If we are not careful, a~single sorting pass takes $\O(n_d + n)$ time, because
+while we have only $n_d$~items to sort, we have to scan all $n$~buckets. This can
+be easily avoided if we realize that the order of the buckets does not need to be
+fixed --- in every pass, we can use a~completely different order and it still
+does bring the equivalent tuples together. Thus we can keep a~list of buckets
+that are used in the current pass and look only inside these buckets. This way,
+we reduce the time spent in a~single pass to $\O(n_d)$ and the whole algorithm
+takes just $\O(\sum_d n_d) = \O(n)$.
+
+Our algorithm can be easily modified for trees with unrestricted degrees.
+We replace the fixed $d$-tuples by general sequences of codes. The first
+sort does not need any changes. In the second sort, we proceed from the first
+position to the last one and after each bucket-sorting pass we put aside the sequences
+that have just ended. They are obviously not equivalent to any other sequences.
+The time complexity of the second sort is linear in the sum of the lengths of the sequences, which is
+$n_{d+1}$ for depth~$d$. We can therefore decide isomorphism of the whole trees
+in time $\O(\sum_d (n_d + n_{d+1})) = \O(n)$.
+
+The unification of sequences by bucket sorting will be useful in many
+other situations, so we will state it as a~separate lemma:
+
+\lemman{Sequence unification}\id{suniflemma}%
+Partitioning of a~collection of sequences $S_1,\ldots,S_n$, whose elements are
+arbitrary pointers and symbols from a~finite alphabet, to equality classes can
+be performed on the Pointer Machine in time $\O(n + \sum_i \vert S_i \vert)$.