Starting from the top or the bottom? Finding a specific paper in a stack. I´m a teacher and I´m constantly grading papers.  We had finals this week and after grading a series of makeup tests (randomly stacked up), I needed to staple the test with another form the school uses (randomly stacked up again).  
So here´s the situation. There are two stacks, let´s say of twenty papers each. Each paper belongs to one student with their respective name.  I pick up the form on top of stack 1 belonging to Bill, and then I look through stack 2, starting from the top down, to find Bill´s make up test.  I find Bill´s makeup test and remove it from the stack.  Then I return to stack 1, pick up Andrea´s form, then rifle through stack 2 until I find Andrea´s makeup test and remove it from the stack. After doing this process for awhile, it would "seem" that the tests I´m looking for in stack 2 tend to be on the bottom and not on the top.  In fact, about half way through, I began to start from the bottom and it would "seem" that I found the wanted test faster that way.
My question is this: Is there really an increased probability of finding the makeup tests in stack 2 starting from the bottom instead of from the top or am I just a lucky observer of Murphy´s law?  Perhaps there is more efficient method, for example looking for the first half of the tests starting from the top, and then the rest from the bottom? 
Thank you for any responses you might have. 
 A: Cool question! With regard to the randomness of stack 2, you are indeed observing Murphy's Law. Given a pile of papers that is randomly stacked, taking some papers out of it leaves a pile that is still randomly stacked. Note that this does not depend on which papers you take out, it is just a consequence of the original pile being randomly stacked.
About the efficiency of your method, I'd say there is no faster way. Say your stacks are of size $N$, then you are using an $\mathcal{O}(N^2)$ method: you walk your way through pile 1, which is $\mathcal{O}(N)$, and per paper in pile 1 you walk your way through pile 2, which is also $\mathcal{O}(N)$, resulting in $\mathcal{O}(N^2)$. Since you need to grade all papers in pile 1, you already "lose" $\mathcal{O}(N)$ there. And there is no faster way than $\mathcal{O}(N)$ to find the corresponding paper in pile 2.
A: Randomness
Let's say there are $N$ papers in each stack. If the papers are completely random, then for any paper in the first stack, there is an equal probability of $\frac{1}{N}$ of finding the corresponding paper in any given position in the second stack: It will be equally likely that the test in stack $2$ corresponding to the top-most form of stack $1$ is at the top of stack $2$ or at the bottom of stack $2$.
This can be a case of:


*

*Bad luck.

*The stacks are not truly random.

*That phenomenom where people only notice the unfortunate cases (for some reason, I always miss the bus by like 10 seconds?).


It might be interesting to keep track of which half of the $2$nd stack you find the paper, you are looking for. In about $50\ \%$ of the cases, it should be in the remaining top half. If you find over some not too short time period that this is not the case, then you are either dealing with some serious bad luck, or there is indeed some non-randomness to the piles.
Alternatives
If you try to find something in an unsorted stack, there is no better way than to simply rifle through the stack until you find what you are looking for. Is this efficient? The nomenclature is: For the problem of finding something in an unsorted stack of size $N$, you might in the worst-case scenario have to riffle through all $N$ papers, since the paper you are looking for might just be last (one says that the complexity of the problem is $\mathcal{O}(N)$). Since you look through the second pile not once, but $N$ times, the total complexity is $\mathcal{O}(N^2)$.
The key-word here is unsorted. One way of improving is that you start out by sorting the second stack. In this manner, all subsequent searches will be much faster (typical efficient searches in a sorted stack has a complexity of $\mathcal{O}(\log(N))$. I know that sorting is not free. The best sorting methods out there (on a random stack) have a complexity of $\mathcal{O}(N\log(N))$, but it might be worth your while, depending on the size of the stacks. For any real human being, sorting a stack will have a complexity of $\mathcal{O}(N^2)$. Once you have sorted the second stack, you will be in business of finding papers very quickly.
Another alternative is: When you riffle through the second stack, you do a semi-sorting at the same time: Whenever a student's name begin with an N or something further along in the alphabet, you just put it to the back of pile. Otherwise leave the paper where it is. Now, when you search for a student, if the student's name begins with an N, or a later letter, start from the back, otherwise start from the front. No matter where you start, you should keep semi-sorting the stack as above, since you will keep increasing the number of papers being in the correct half. My feeling is that this last method is the best in practise.
Lastly, there is of course the possibility of sorting both stacks. Doing this makes the task of pairing papers from the two stacks very easy and satisfying, as you only need to keep pairing the top-most papers in each stack and put them aside.
