Stack can be sorted in O(n^2). @sankalp: Stack can always be sorted. Why do you think it cant be in some cases ?
One can think like insertion sort algo : 1. for i in (1,n) 2. Pop up the top n-1 element and keep nth element in global variable say "hold" 3. while pushing get the position for "hold" and push it there for loop will take O(n) and step 2 will take take O(n) time. So overall O(n^2) complexity Program can be done with recursion using a variable (hence O(1) space). But it will use system stack :) Any comments OR better solution is welcomed?? -- Regards Jitendra Kushwaha MNNIT, Allahabad -- 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.
