Asymptotic performance When n gets large enough, a @(n2)algorithm always beats a o(n)algorithm
Asymptotic performance When n gets large enough, a Θ ( n 2 ) algorithm always beats a Θ ( n 3 ) algorithm. n 0 T( n )
Merge sort MERGE-SORT ALI.n 1. Ifn=1. done 2. Recursively sort A[1.[n/211 andA[/2」+1.n] 3. Merge the 2 sorted lists Key subroutine: MERGE
Merge sort 1. If n = 1, done. 2. Recursively sort A[1 .. ] and A[ + 1 .. n ] 3. "Merge" the 2 sorted lists. Key subroutine: MERGE ⎡⎢n / 2⎤⎥ ⎢⎣n / 2⎥⎦ MERGE-SORT A[1 .. n]
Merging two sorted arrays 20122012‖20122012‖2012‖20(12 131113 113113n|u@|n3 7979⑦9⊙ 2 2 7 1.2.7.9.11.12.13.20 Time=o(n to merge a total of n elements (linear time)
Merging two sorted arrays 20 12 13 11 7 9 2 1 20 12 13 11 7 9 2 20 12 13 11 7 9 20 12 13 11 9 20 12 13 11 20 12 13 1 2 7 9 11 12 Time = Θ ( n ) to merge a total of n elements (linear time). 1, 2, 7, 9, 11, 12, 13, 20
Operation of merge sort sorted sequence 127911121320 merge 791220 121113 merge merge 1220 79 1113 12 merge merge\ merge merge\ 2012 9 132 initial sequence
Operation of merge sort 20 12 7 9 11 13 2 1 initial sequence 1 2 7 9 11 12 13 20 sorted sequence merge 7 9 12 20 1 2 11 13 merge merge 12 20 7 9 11 13 1 2 merge merge merge merge
Analyzing merge sort MERGE-SORT 1. Ifn=1. done 2T(n/2) 2. Recursively sort A[1. [n/21] and A[Ln/2+I.n] 3.Merge the 2 sorted lists Sloppiness: Should be T( n/2)+T(n/2 ),but it turns out not to matter asymptotically
Analyzing merge sort 1. If n = 1, done. 2. Recursively sort A[1 .. ] and A[ + 1 .. n ] 3. "Merge" the 2 sorted lists. ⎡⎢n / 2 ⎤⎥ ⎢⎣ n / 2⎥⎦ T( n ) MERGE-SORT A[1 .. n ] Θ(1) 2 T( n/2) Θ ( n ) Sloppiness: Should be , but it turns out not to matter asymptotically. Tn Tn ( /2 ) ( /2 ) ⎡⎢ ⎤ ⎢⎥ ⎥ ⎣⎦ +