sorting algorithms we have just seen that if we happen to know that list is sortedwe can exploit that information to greatly reduce the time needed to search list does this mean that when asked to search list one should first sort it and then perform the searchlet (sortcomplexity( )be the complexity of sorting list since we know that we can always search list in (len( )timethe question of whether we should first sort and then search boils down to the questionis (sortcomplexity(llog(len( ))len( )the answersadlyis no one cannot sort list without looking at each element in the list at least onceso it is not possible to sort list in sub-linear time does this mean that binary search is an intellectual curiosity of no practical importhappilyno suppose that one expects to search the same list many times it might well make sense to pay the overhead of sorting the list onceand then amortize the cost of the sort over many searches if we expect to search the list timesthe relevant question becomesis (sortcomplexity(lk*log(len( ))less than *len( )as becomes largethe time required to sort the list becomes increasingly irrelevant how big needs to be depends upon how long it takes to sort list iffor examplesorting were exponential in the size of the listk would have to be quite large fortunatelysorting can be done rather efficiently for examplethe standard implementation of sorting in most python implementations runs in roughly ( *log( )timewhere is the length of the list in practiceyou will rarely need to implement your own sort function in most casesthe right thing to do is to use either python' built-in sort method ( sort(sorts the list lor its built-in function sorted (sorted(lreturns list with same elements as lbut does not mutate lwe present sorting algorithms here primarily to provide some practice in thinking about algorithm design and complexity analysis we begin with simple but inefficient algorithmselection sort selection sortfigure works by maintaining the loop invariant thatgiven partitioning of the list into prefix ( [ : ]and suffix ( [ + :len( )])the prefix is sorted and no element in the prefix is larger than the smallest element in the suffix