we can still use treesort howeverto output the sorted items into the original arraywe will need another procedure fillarray(tree tarray aint jto traverse the tree and fill the array that is easiest done by passing and returning an index that keeps track of the next array position to be filled this results in the complete treesort algorithmtreesort(array at emptytree for size(ai+ insert( [ ],tfillarray( , , fillarray(tree tarray aint jif not isempty(tj fillarray(left( ), ,ja[ ++root(tj fillarray(right( ), ,jreturn which assumes that is pointer to the array location and that its elements can be accessed and updated given that and the relevant array index since there are items to insert into the treeand each insertion has time complexity (log )treesort has an overall average time complexity of (nlog nsowe already have one algorithm that achieves the theoretical best average case time complexity of (nlog nnotehoweverthat if the tree is not kept balanced while the items are being insertedand the items are already sortedthe height of the tree and number of comparisons per insertion will be ( )leading to worst case time complexity of ( )which is no better than the simpler array-based algorithms we have already considered exercisewe have assumed so far that the items stored in binary search tree must not contain any duplicates find the simplest ways to relax that restriction and determine how the choice of approach affects the stability of the associated treesort algorithm heapsort we now consider another way of implementing selection sorting algorithm using more efficient data structure we have already studied the underlying idea here is that it would help if we could pre-arrange the data so that selecting the smallest/biggest entry becomes easier for thatremember the idea of priority queue discussed earlier we can take the value of each item to be its priority and then queue the items accordingly thenif we remove the item with the highest priority at each step we can fill an array in order 'from the rear'starting with the biggest item priority queues can be implemented in number of different waysand we have already studied straightforward implementation using binary heap trees in howeverthere may be better wayso it is worth considering the other possibilities