Class Code: AMC621 Instructor: Huilan Chang

Introduction

• Sorting $n$ numbers requires $Ω(n)$ time because input these $n$ numbers requires $Ω(n)$ time.
• Sorting in linear time means to sort $n$ numbers in $O(n)$ time.
• We will prove that insertion sort, mergesort, heapsort, and quicksort takes $Ω(n \lg n)$ time.
• These algorithms share an interesting property: The sorted order they determine is based only on comparisons between the input elements. We call such sorting algorithms comparison sorts or comparison-based sorting algorithms.
• 總之, insertion sort, mergesort, heapsort, and quicksort並沒有事先就對input numbers有了解、有假設; 都是採用”取兩個數比大小”的方式完成排序, 因此又被稱為comparison sorts.
• Insertion sort, merge sort, heapsort, and quicksort are general sorting algorithms.
• 只花 $θ(n)$ time的sorting algorithms都是事先就對input numbers有了解、有假設。利用input numbers的特殊性質來設計演算法，而不是採用comparison sort.

Lower bounds for sorting（指comparison sorts）

• Assume that input numbers are $a_1, a_2, \cdots, a_n$, and they are distinct.
• Any comparison sort can be described by a computation tree/decision tree (討論下界的重要方法).

<aside> ⭐

In a decision tree:

• Each internal node is annotated by $i:j$ for some $i$ and $j$ (which means that $a_i$ is compared with $a_j$).
• If $a_i\leq a_j$, then go to the left; if $a_i>a_j$ , then go to the right.
• Each external node is annotated by a permutation $<\pi(1), \pi(2), \cdots, \pi(n)>$(indicating that the result of sorting is $a_{\pi(1)}, a_{\pi(2)}, \cdots, a_{\pi(n)}$ ). </aside>

Ÿ

For example, the following is the decision tree for insertion sort when $n = 3$.

<aside> ⭐

Theorem 1. Any comparison sort algorithm requires $Ω(n \lg n)$ comparisons in the worst case if the instances have length $n$.

</aside>