up the values working from the outside inall of the pairs add to since there are numbersthere must be pairs that means the sum of all the pairs is ( + you can see that the final formula contains an term that means that the number of steps in the algorithm is proportional to the square of the size of the list if the size of the list doublesthe number of steps quadruples if the size triplesit will take nine times as long to finish computer scientists call this quadratic or algorithm let' see how that compares to the merge sort algorithm in the case of merge sortwe divided list into two pieces and sorted the individual pieces before merging them together the real work is done during the merge process when the values in the sublists are copied back into the original list figure depicts the merging process to sort the list [ the dashed lines show how the original list is continually halved until each item is its own list with the values shown at the bottom the single-item lists are then merged back up into the two item lists to produce the values shown in the second level the merging process continues up the diagram to produce the final sorted version of the list shown at the top figure merges required to sort [ the diagram makes analysis of the merge sort easy starting at the bottom levelwe have to copy the values into the second level from the second to third levelthe values need to be copied again each level of merging involves copying values the only question left to answer is how many levels are therethis boils down to how many times list of size can be split in half you already know from the analysis of binary search that this is just log thereforethe total work required to sort items is log computer scientists call this an log algorithm so which is going to be betterthe selection sort or the log merge sortif the input size is smallthe selection sort might be little faster because the code is simpler and there is less overhead what happensthough as gets largerwe saw in the analysis of binary search that the log function grows very slowly (log so (log nwill grow much slower than