2024/10/6ReviewoflastclassDivideAndConquer(I)GoalsoftheLectureExampleExamples(cont.)ImprovementalgorithmImprovementalgorithm(cont.)Examples(cont.)Examples(cont.)Divide-and-ConquerTechniqueDivide-and-ConquerTechnique(cont.)Divide-and-ConquerTechnique(cont.)GeneralDivide-and-ConquerRecurrenceMergeSort2024/10/6TheMergeSortAlgorithmHowtoMergeTwoSortedListIntuitiveMergeListsExampleTheMergeListsAlgorithmTheMergeListAlgorithm(cont.)MergeListsAnalysisMergeSortAnalysisMergeSortAnalysis(cont.)HowaboutAverage-CaseAnalysis?CommenttoMergeSortTheEndAssignments