some simple algorithms and data structures def merge(leftrightcompare)"""assumes left and right are sorted lists and compare defines an ordering on the elements returns new sorted (by comparelist containing the same elements as (left rightwould contain ""result [ , while len(leftand len(right)if compare(left[ ]right[ ])result append(left[ ] + elseresult append(right[ ] + while ( len(left))result append(left[ ] + while ( len(right))result append(right[ ] + return result import operator def mergesort(lcompare operator lt)"""assumes is listcompare defines an ordering on elements of returns new sorted list containing the same elements as ""if len( return [:elsemiddle len( )// left mergesort( [:middle]compareright mergesort( [middle:]comparereturn merge(leftrightcomparefigure merge sort let' analyze the complexity of mergesort we already know that the time complexity of merge is (len( )at each level of recursion the total number of elements to be merged is len(lthereforethe time complexity of mergesort is (len( )multiplied by the number of levels of recursion since mergesort divides the list in half each timewe know that the number of levels of recursion is (log(len( )thereforethe time complexity of mergesort is ( *log( ))where is len(lthis is lot better than selection sort' (len( ) for exampleif has , elementslen( ) is hundred million but len( )*log (len( )is about , this improvement in time complexity comes with price selection sort is an example of an in-place sorting algorithm because it works by swapping the place of elements within the listit uses only constant amount of extra storage (one element in our implementationin contrastthe merge sort algorithm