Decision-tree example Sort(a1, a2, a3) 1:2 =〈9,4,6) 2:3 1:3 123 1:3 213 2:3 132 312 231 321 4<6≤9 Each leaf contains a permutation〈π(1),2丌(2)2…,m(m)to indicate that the ordering an< (2) has been established o 2001 by Charles E Leiserson Introduction to Algorithms Day 8 L5.7© 2001 by Charles E. Leiserson Introduction to Algorithms Day 8 L5.7 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 leaf contains a permutation 〈π(1), π(2),…, π(n)〉 to indicate that the ordering aπ(1) ≤ aπ(2) ≤ L ≤ aπ(n) has been established. 4 ≤ 6 ≤ 9 Sort 〈a1, a2, a3〉 = 〈 9, 4, 6 〉: