A linear walk can notice and preserve the cyclic walk else abort. For what disorder distribution do you want to do better? If you have such a field as you describe radix sort is linear time, as discussed in TAOCP. On Fri, Apr 20, 2018 at 12:56 PM Henry Baker <hbaker1@pipeline.com> wrote:
Suppose you have N records in which one of the fields is a number 0..(N-1), and there is exactly one record for each number 0..(N-1).
It is trivial to sort such a set using traditional Knuth-TAOCP algorithms.
However, if I don't care that the first record is labelled "0", but only care that the final ordering preserves the *cyclic* ordering of the group, can I do any better?
Obviously, I can't do a lot better, since cyclicly rotating the ordering costs O(N), while sorting costs O(NlogN), but is there a clever way to sort w/o putting "0" at the front and "(N-1)" at the end? In particular, is there a way to sort that automatically notices when the records are already in cyclic order, and doesn't bother making any further changes.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- -- http://cube20.org/ -- http://golly.sf.net/ --