@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 wrote:
> Also, you can choose not to use a
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
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
@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 ema
