Decision-tree example Sort(a1, a2, a3) 1:2 =〈9,4,6) 2:3 1:3 123 1:3 213 4≤6 2:3 132 312 231 321 Each internal node is labeled i; i for i,jE(1,2, ..,n) The left subtree shows subsequent comparisons ifa s a The right subtree shows subsequent comparisons if a; 2a o 2001 by Charles E Leiserson Introduction to Algorithms Day 8 L5.6© 2001 by Charles E. Leiserson Introduction to Algorithms Day 8 L5.6 Decision-tree example 1:21:2 2:3 2:3 123 123 1:31:3 132 132 312 312 1:3 1:3 213 213 2:32:3 231 231 321 321 Each internal node is labeled i:j for i, j ∈ {1, 2,…, n}. •The left subtree shows subsequent comparisons if ai ≤ aj. •The right subtree shows subsequent comparisons if ai ≥ aj. 4 ≤ 6 Sort 〈a1, a2, a3〉 = 〈 9, 4, 6 〉: