Introduction to Algorithms
6.046J/18.401J/SMA5503
Lecture 5
Prof. Erik Demaine
Introduction to Algorithms Day 8 L5.2© 2001 by Charles E. Leiserson
How fast can we sort?
All the sorting algorithms we have seen so far
are comparison sorts: only use comparisons to
determine the relative order of elements.
• E.g., insertion sort, merge sort, quicksort,
heapsort.
The best worst-case running time that we’ve
seen for comparison sorting is O(n lg n) .
Is O(n lg n) the best we can do?
Decision trees can help us answer this question.
Introduction to Algorithms Day 8 L5.3© 2001 by Charles E. Leiserson
Decision-tree example
1:2
1:2
2:3
2:3
123
123
1:3
1:3
132
132
312
312
1:3
1:3
213
213
2:3
2: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 a
i
≤ a
j
.
• The right subtree shows subsequent comparisons if a
i
≥ a
j
.
Sort 〈a
1
, a
2
, …, a
n
〉
Introduction to Algorithms Day 8 L5.4© 2001 by Charles E. Leiserson
Decision-tree example
1:2
1:2
2:3
2:3
123
123
1:3
1:3
132
132
312
312
1:3
1:3
213
213
2:3
2: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 a
i
≤ a
j
.
• The right subtree shows subsequent comparisons if a
i
≥ a
j
.
9 ≥ 4
Sort 〈a
1
, a
2
, a
3
〉
= 〈 9, 4, 6 〉:
Introduction to Algorithms Day 8 L5.5© 2001 by Charles E. Leiserson
Decision-tree example
1:2
1:2
2:3
2:3
123
123
1:3
1:3
132
132
312
312
1:3
1:3
213
213
2:3
2: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 a
i
≤ a
j
.
• The right subtree shows subsequent comparisons if a
i
≥ a
j
.
9 ≥ 6
Sort 〈a
1
, a
2
, a
3
〉
= 〈 9, 4, 6 〉:
