# Efficiently converting an ascending sequence to a sorted sequence one at a time

I wondered...

Lets say you have a machine, which sometimes prints out the time on a piece of paper in the following format: $$year-month-day-hours-minutes-seconds.$$

For example today it would print something like $$11-12-27-20-03-58,$$ then maybe two and a half hour later $$11-12-27-22-45-32,$$ and so on. You're investigating this machine and collect all the output it gives you. For convenience you write down a running number on the backs of these papers. This way you can sort and find the prints much faster. On the first ever print you wrote #1, on the second one you wrote #2, etc. When you reached #9999 you decided to switch to hexadecimal numbers to safe some space.

Then you have a better idea: You write a program to automatize this. Whenever the machine prints out a new time, the programm should write down which print it is in the above sense. There is only one problem: The program you'll write can't count, i.e. remember how many prints it has done. However, the program has access to the time printed on the paper. So it could just use the time itself to encode the order. But this is probably a waste of space.

Here the question: How can you optimally use the information you got to convert it into a sorted series, even if every time you only have access to the current print?

How can the solution to this specific problem be generalized? (i.e. not necessarily relying on this example, where the input is a time.)

• The only information known is the current printed time? – Michael Blondin Dec 28 '11 at 3:12
• There is no nontrivial solution. If you are not allowed any extra memory, then you cannot distinguish, even in principle, between a machine that spits out exactly one slip of paper and then dies (which requires NO bits to be written), and a machine that spits out one slip of paper every second for 10000 years (which requires as many bits as the times themselves). – Jeffε Dec 28 '11 at 10:49
• Just a (fool?) idea that works with time: whenever you receive a timestamp you can start a "private stopwatch", then, when a new timestamp arrives, subtract the stopwatch value from it and add 1 (and reset the stopwatch) ... this will help you to save some bits (suppose you receive 00'58", 01'30", 10'10" you print 58,59,131 instead of 58,130,1010). It can be generalized if you know the difference between the current and the last value received. Otherwise, without any memory "from the past", I think that all you can do is copy the data you receive. – Marzio De Biasi Dec 28 '11 at 13:46
• @Vor: Your strategy is identical to always writing down the previous time stamp plus 1. Even if a private stopwatch is allowed by the model of computation (a bit of stretch in my opinion), the long-term savings are insignificant. – Jeffε Dec 29 '11 at 12:37
• @JɛﬀE Yes but could this machine handle 10000 years and more importantly how it handles it. Is it vulnerable to a millenium-like problem (because then we would have to use additional information to keep track of how many time the clock made a full period)? I hope Nikolaj can clarify this point or we can consider the case with no overlaps and then solve the more complicated one. – chazisop Dec 29 '11 at 13:33

By using the adversary method, the last generated time could be the previous object in the ordering of your preference. Therefore, in order to distinguish between any two numbers (and thus be able to order them) you would have to use information equivalent to the length of the full representation.

I believe that this question is related to issues in databases and relational algebra such as primary key selection. I don't think you need to refrain to pure information-theory arguments in order to solve this problem.

From a distance, it looks somewhat like this to me:

Let there be a constant defined at the beginning, set to the real time clock value at program start.

Include with each output generated, the difference between the value to be printed and this constant (in hex if you like), which actually is the unique value of time elapsed since program start.

That should serve the purpose? This is not a generalized algorithm, though.

• What's a "real time clock"? – Jeffε Dec 29 '11 at 12:37
• The system clock -- providing the system time. You could read it as "... set to system time at program start" in the sentence above. – Kris Dec 29 '11 at 12:56
• What's a "system clock"? What is "system time"? (Keep in mind that this is a forum for questions in theoretical computer science. The standard theoretical model of computation does not have a system clock. While it is possible to simulate such a clock with an instruction counter, the original question explicitly forbids counters.) – Jeffε Dec 29 '11 at 13:21
• @JɛﬀE See the answer by chazisop -- "I don't think you need to refrain to pure information-theory arguments in order to solve this problem." – Kris Mar 29 '14 at 5:51