@Wan: Storing the elements as link list rather than array requires additional space.
If we are taking extra O(n) space, then the usual approach of merging two sorted arrays in O(n) time and memory will suffice. On Fri, Aug 27, 2010 at 5:18 PM, Yan Wang <wangyanadam1...@gmail.com> wrote: > Also, you can choose not to use a tree here. Just sort the remaining > √n elements first, then insert these √n elements sequentially into the > n-√n elements' array. The essential here is to store all these > elements in a linked list rather than an array, because using an array > the program always needs to do a lot of element shifting manipulations > which is a time-consuming thing. > > On Fri, Aug 27, 2010 at 4:40 AM, Yan Wang <wangyanadam1...@gmail.com> > wrote: > > We can turn the sorted array with first (n − √n) elements recursively > > to a balanced binary sorting tree. This can be done by choosing the > > median as the pivot in every step and then recursively manipulate the > > left half array and right half array in this way. For a sorted array, > > to find its median is an easy action with constant time complexity. > > Thus this procedure will cost O(n-√n) time. At last, we insert the > > remaining √n elements into the tree, this will cost O(√n * log(n - > > √n)) time. So the ultimate time complexity will be O(n). > > > > On Thu, Aug 26, 2010 at 9:56 PM, Rahul Singal <rahulsinga...@gmail.com> > wrote: > >> @saurav > >> > >> I dont think in place approach is possible . This will end up taking n^2 > >> time . > >> > >> -- > >> 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<algogeeks%2bunsubscr...@googlegroups.com> > . > >> For more options, visit this group at > >> http://groups.google.com/group/algogeeks?hl=en. > >> > > > > -- > 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<algogeeks%2bunsubscr...@googlegroups.com> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- 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.
