Class Code: AMC621 Instructor: Huilan Chang

<aside>

Divide-and-conquer approach 分而治之方法 ****involves the following three steps.

• Divide an instance of a problem into some smaller instances of the original problem.
• Conquer: Find a solution to each smaller instance.
• Combine: Obtain a solution to the original problem by combing the solutions to smaller instances.

🔹 The process of dividing the instances continues until they are so small that a solution is readily obtainable.

</aside>

◼️ Mergesort

Sorting 排序(由小到大)

🔹Strategy Three steps:

1. Divide the array陣列 into two subarrays with $\lfloor n/2\rfloor$ and $\lceil n/2\rceil$ items, respectively.
2. Conquer each subarray by sorting it. Use recursion遞迴 to do this until the array has size 1.
3. Combine (merge) the solutions to the subarrays into a single sorted array.

Example. $n=8$ and $A=[27, 10, 12, 20, 25, 12, 15, 22]$. MERGE-SORT($A$, 0, 7)

🔹Pseudocode

MERGE-SORT($A, p, r$)

▶️Google Colab

MERGE($A, p, q, r$)

🔹Analysis Basic operation: the comparison of an item in $L$ and an item in $R$.

• The worst-case time complexity of MERGE($A, p, q, r)$ is $W(p, q, r) = r-p +1$. Therefore, the worst-case time complexity of “merge” is $\Theta(r-p)$.
• MERGE-SORT

Let $W(n)$ be the number of comparisons in the worst-case when the input size is $n$. Then ✏️ $W(n)=\Theta(n\lg n).$ Why?

<aside>

A sorting algorithm is in-place (原位排序) if it does not use any extra space beyond needed storage.

The mergesort is not in-place, because it uses extra spaces $L$ and $R$.

</aside>

◼️ Quicksort (partition-exchange sort)