Before revision:  The sorting algorithm returns the given numbers in sorted order  stored within a bit-vector of N bits  whereas our ranking algorithms construct data structures that allows us subsequently to return the (dense) rank of each number x in S in constant time if the position of x in S is given together with x. As an application of our algorithms we give an algorithm for tree isomorphism that runs in O(n) time and uses O(n) bits on n-node trees  .
After revision:  The sorting algorithm returns the given numbers in sorted order stored within a bit-vector of N bits whereas our ranking algorithms construct data structures that allows us subsequently to return the (dense) rank of each number x in S in constant time if the position of x in S is given together with x. As an application of our algorithms we give an algorithm for tree isomorphism that runs in O(n) time and uses O(n) bits on n-node trees . The previous best linear-time algorithm for tree isomorphism uses \Theta(n \log n) bits .