itemsso we are asking how many ways there are of arranging items the first item can be any of the itemsthe second can be any of the remaining itemsand so forthso their total number is ( )( nthus we want to know the height of binary tree that can accommodate as many as nleaves the number of leaves of tree of height is at most so we want to find such that >nh >log ( !or there are numerous approximate expressions that have been derived for log ( !for large nbut they all have the same dominant termnamely nlog (remember thatwhen talking about time complexitywe ignore any sub-dominant terns and constant factors henceno sorting algorithm based on comparing items can have better average or worst case performance than using number of comparisons that is approximately nlog for large it remains to be seen whether this (nlog ncomplexity can actually be achieved in practice to do thiswe would have to exhibit at least one algorithm with this performance behaviour (and convince ourselves that it really does have this behaviourin factwe shall shortly see that there are several algorithms with this behaviour we shall proceed now by looking in turn at number of sorting algorithms of increasing sophisticationthat involve the various strategies listed above the way they work depends on what kind of data structure contains the items we wish to sort we start with approaches that work with simple arraysand then move on to using more complex data structures that lead to more efficient algorithms bubble sort bubble sort follows the exchange sort approach it is very easy to implementbut tends to be particularly slow to run assume we have array of size that we wish to sort bubble sort starts by comparing [ - with [ - and swaps them if they are in the wrong order it then compares [ - and [ - and swaps those if need beand so on this means that once it reaches [ ]the smallest entry will be in the correct place it then starts from the back againcomparing pairs of 'neighbours'but leaving the zeroth entry alone (which is known to be correctafter it has reached the front againthe second-smallest entry will be in place it keeps making 'passesover the array until it is sorted more generallyat the ith stage bubble sort compares neighbouring entries 'from the back'swapping them as needed the item with the lowest index that is compared to its right neighbour is [ - after the ith stagethe entries [ ], [ - are in their final position at this point it is worth introducing simple 'test-caseof size to demonstrate how the various sorting algorithms work bubble sort starts by comparing [ ]= with [ ]= since they are not in orderit swaps themgiving it then compares [ ]= with [ ]= since those are in orderit leaves them where they are then it compares [ ]= with [ ]= and those are not in order once againso they have to be swapped we get note that the smallest entry has reached its final place this will always happen after bubble sort has done its first 'passover the array