title: Algorithm to all N words in a language
body: <p>Suppose you have invented a language, and are writing a dictionary of all N words in the language.  The dictionary has N pages, one for each word.  You have handwritten your dictionary pages and have put them into a stack A in alphabetical order, with the first word's page on the top of the stack.  You take the stack to the printing store to have it professionally printed.  Unfortunately, the clerk at the store drops the stack, and it breaks into two smaller stacks A1 and A2 of possibly different sizes.  To fix the problem, the clerk randomly picks one stack and puts it on top of the other, creating a new stack B.  (Assume both sub-stacks are still in alphabetical order- i.e., neither of them flipped upside down).  It is possible that B = A, but it is also possible that the pages in B are now in the wrong order (e.g., if A1 should have been on top and now A2 is on top); and what's worse, you no longer know where the line between A1 and A2 originally was. Design an efficient, optimal algorithm to determine to tell whether B is in the right order; and if not, to determine where to split B back into A1 and A2 so that they can be put back together properly.  What is the worst-case running time of your algorithm, as a function of N?</p>