some simple algorithms and data structures we use induction to reason about loop invariants base caseat the start of the first iterationthe prefix is emptyi the suffix is the entire list the invariant is (triviallytrue induction stepat each step of the algorithmwe move one element from the suffix to the prefix we do this by appending minimum element of the suffix to the end of the prefix because the invariant held before we moved the elementwe know that after we append the element the prefix is still sorted we also know that since we removed the smallest element in the suffixno element in the prefix is larger than the smallest element in the suffix when the loop is exitedthe prefix includes the entire listand the suffix is empty thereforethe entire list is now sorted in ascending order def selsort( )"""assumes that is list of elements that can be compared using sorts in ascending order""suffixstart while suffixstart !len( )#look at each element in suffix for in range(suffixstartlen( ))if [il[suffixstart]#swap position of elements [suffixstart] [il[ ] [suffixstartsuffixstart + figure selection sort it' hard to imagine simpler or more obviously correct sorting algorithm unfortunatelyit is rather inefficient the complexity of the inner loop is (len( )the complexity of the outer loop is also (len( )sothe complexity of the entire function is (len( ) it is quadratic in the length of merge sort fortunatelywe can do lot better than quadratic time using divide-andconquer algorithm the basic idea is to combine solutions of simpler instances of the original problem in generala divide-and-conquer algorithm is characterized by threshold input sizebelow which the problem is not subdivided the size and number of sub-instances into which an instance is splitand the algorithm used to combine sub-solutions the threshold is sometimes called the recursive base for item it is usual to consider the ratio of initial problem size to sub-instance size in most of the examples we've seen so farthe ratio was but not the most inefficient of sorting algorithmsas suggested by successful candidate for the presidency see