CSE310 Lecture 07: MergesortTopics of this lectureDivide and Conquer Design TechniqueMerge SortMerge Sort AlgorithmComplexity of Merge-Sort AlgorithmIterative Version of [email protected] Lecture 07:CSE310 Lecture 07:MergesortMergesortGuoliang (Larry) XueDepartment of CSEArizona State Universityhttp://optimization.asu.edu/[email protected] of this lectureTopics of this lectureMerge and MergesortMerging in linear timeMergesortWorst-case analysisBest-case analysisAverage-case analysisRecursive or [email protected]Recursion: An algorithm calls itself one or several times to deal with closely related sub-problems Divide and Conquer: •Divide: break a problem into several smaller sub-problems•Conquer: solve these sub-problems recursively •Combine: combine these solutionsMerge Sort: Use divide-and-conquer technique to sort elementsDivide and Conquer Design TechniqueDivide and Conquer Design [email protected]Divide: Divide the n-element sequence into 2 subsequences of n /2 each;Conquer: Sort each subsequence recursively using merge sortCombine: Merge two sorted subsequences to produce a single sorted sequenceMerge SortMerge Sort5, 3, 6, 8, 12, 3, 1, 4, 7, 9, 143, 5, 6, 8, 12 1, 3, 4, 7, 9, 141, 3, 3, 4, 5, 6, 7, 8, 9, 12, [email protected] Sort AlgorithmMerge Sort Algorithmmerge-sort (A, L, R) IF R > L THEN M := (R+L)/2merge-sort (A, L, M)merge-sort (A, M+1, R)merge(A, L, M, R)5 2 4 6 1 3 2 65 2 4 6 1 3 2 65 2 4 6 1 3 2 65 2 4 6 1 3 2 62 5 4 6 1 3 2 62 4 5 6 1 2 3 61 2 2 3 4 5 6 6merge (A, l, m, r) n1=m-l+1 n2=r-m new L[1..n1+1] and R[1..n2+1] L[1..n1]=A[l..m] R[1..n2]=A[m+1..r] L[n1+1]= R[n2+1]= i=1; j=1; for k=l to r do if L[i] <= R[j] A[k] = L[i]; i++; else A[k] = R[j]; j++; endfor5 2 4 6 1 3 2 [email protected]Time needed for size n problem is T (n)The base case (n = 1): (1)Time needed to divide the problem: D(n) = (1)Time needed for 2 subproblems is 2T(n/2)Time needed to combine solutions: C(n) = (n)Complexity of Merge-Sort AlgorithmComplexity of Merge-Sort AlgorithmotherwisennTnifnT)2/(21)1()(Solution to the recurrence isT(n) = (nlgn)[email protected] Version of MergesortIterative Version of MergesortA list of length 1 is sorted.We can merge two sorted lists of length k into on sorted list of length 2k.We go from bottom layer (n sorted lists of length 1) to the top layer (one sorted list of length n)It takes O(n) time to go from one layer to the upper layer.It takes O(log n) [email protected]Mergesort—O(n log n) time algorithm.Recursive or [email protected]The materials covered in this lecture can be found in Section
View Full Document
Unlocking...