CSE310 Lecture 07 Mergesort Guoliang Larry Xue Department of CSE Arizona State University http optimization asu edu xue Guoliang Xue asu edu Topics of this lecture Merge and Mergesort Merging in linear time Mergesort Worst case analysis Best case analysis Average case analysis Recursive or Iterative 2 Guoliang Xue asu edu Divide and Conquer Design Technique 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 solutions Merge Sort Use divide and conquer technique to sort elements Guoliang Xue asu edu 3 Merge Sort Divide Divide the n element sequence into 2 subsequences of n 2 each Conquer Sort each subsequence recursively using merge sort Combine Merge two sorted subsequences to produce a single sorted sequence 5 3 6 8 12 3 5 6 8 12 3 1 4 7 9 14 1 3 4 7 9 14 1 3 3 4 5 6 7 8 9 12 14 4 Guoliang Xue asu edu Merge Sort Algorithm merge sort A L R IF R L THEN M R L 2 merge sort A L M merge sort A M 1 R merge A L M R 5 52461326 5246 1326 52 46 13 26 2 4 6 13 2 6 25 46 13 26 2456 1236 12234566 5 merge 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 endfor L M R A 5246 1326 Guoliang Xue asu edu Complexity of Merge Sort Algorithm 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 1 if n 1 T n 2T n 2 n otherwise Solution to the recurrence is T n nlgn 6 Guoliang Xue asu edu Iterative Version of Mergesort A 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 steps 7 Guoliang Xue asu edu Summary Mergesort O n log n time algorithm Recursive or iterative 8 Guoliang Xue asu edu Readings The materials covered in this lecture can be found in Section 2 3 9 Guoliang Xue asu edu
View Full Document
Unlocking...