On Tue, Aug 14, 2012 at 2:35 PM, Ian Clark <[email protected]> wrote: > Maybe the IBM 1130 card-sorting program was no cleverer than this (I > never used it that much), but I have a strong feeling it's possible to > do much better.
If the machine has enough memory to store a complete representation of the deck, along with intermediate results about its organization, the first pass is a hit/miss thing, you can impose some amount of order, but until it's complete you do not know how big your deck is, nor how it is organized. After that, you can start optimizing. Obviously, if the deck is already sorted, you're done. Also, if the deck was in reverse order, you're going to have to do a lot of work. I think if the deck was in reverse order, you are going to have to do at least log2(length) passes on the deck, to get it in sorted order. If we treat sorted subsequences in the deck as "a single card" -- the resulting length will tell us about how many passes are needed, at minimum, to sort it. On the other hand, if you can't represent the entire deck in memory, sorting one bit per pass is about the best you can do (except that I think you can keep an intermediate result specifying the the next bit that needs sorted. In other words, if you have 32 bit values that need to be sorted, you might not need 32 passes to sort them all. -- Raul ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
