I would use Insertion sort if the Library gurantees Insertion in O(1). Practically, I do that in Library push a book somewhere in middle. Then the recurrence so obtained is : T(n) = T(n-1) + O(1) which gives O(n) time complexity.
PS: It also speaks about Lateral thinking and whatever they call it. Out of the Box thinking :P -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.