Hi,

The situation is as follows:-

We have n number and we have print them in sorted order. We have access to balanced dictionary data structure, which supports the operations serach, insert, delete, minimum, maximum each in O(log n) time.

We want to retrieve the numbers in sorted order in O(n log n) time using only the insert and in-order traversal.

The answer to this is:-

Sort()
  initialize(t)
  while(not EOF)
     read(x)
     insert(x,t);
  Traverse(t);

Now the query is if we read the elements in time "n" and then traverse the elements in "log n"(in-order traversal) time,, then the total time for this algorithm (n+logn)time, according to me.. Please explain the follow up of this algorithm for the time calculation.. How it will sort the list in O(nlogn) time??

Thanks.