sorting algorithm stability one often wants to sort items which might have identical keys ( ages in yearsin such way that items with identical keys are kept in their original orderparticularly if the items have already been sorted according to different criteria ( alphabeticalsoif we denote the original order of an array of items by subscriptswe want the subscripts to end up in order for each set of items with identical keys for exampleif we start out with the array [ ]it should be sorted to [ and not to [ sorting algorithms which satisfy this useful property are said to be stable the easiest way to determine whether given algorithm is stable is to consider whether the algorithm can ever swap identical items past each other in this waythe stability of the sorting algorithms studied so far can easily be establishedbubble sort this is stable because no item is swapped past another unless they are in the wrong order so items with identical keys will have their original order preserved insertion sort this is stable because no item is swapped past another unless it has smaller key so items with identical keys will have their original order preserved selection sort this is not stablebecause there is nothing to stop an item being swapped past another item that has an identical key for examplethe array [ would be sorted to [ which has items and in the wrong order the issue of sorting stability needs to be considered when developing more complex sorting algorithms often there are stable and non-stable versions of the algorithmsand one has to consider whether the extra cost of maintaining stability is worth the effort treesort let us now consider way of implementing an insertion sorting algorithm using data structure better suited to the problem the idea herewhich we have already seen beforeinvolves inserting the items to be sorted into an initially empty binary search tree thenwhen all items have been insertedwe know that we can traverse the binary search tree to visit all the items in the right order this sorting algorithm is called treesortand for the basic versionwe require that all the search keys be different obviouslythe tree must be kept balanced in order to minimize the number of comparisonssince that depends on the height of the tree for balanced tree that is (log nif the tree is not kept balancedit will be more than thatand potentially (ntreesort can be difficult to compare with other sorting algorithmssince it returns treerather than an arrayas the sorted data structure it should be chosen if it is desirable to have the items stored in binary search tree anyway this is usually the case if items are frequently deleted or insertedsince binary search tree allows these operations to be implemented efficientlywith time complexity (log nper item moreoveras we have seen beforesearching for items is also efficientagain with time complexity (log