京都大学 情報学研究科 知能情報学専攻 2023年2月実施 基礎科目 F2-1

标签：

• Kyoto-University
• Merge-Sort
• Quick-Sort
• Algorithm-Complexity
• Linked-List

Author

祭音Myyura (co-authored with GPT 5.6 SOL)

Description

Answer the following questions about merge sort in ascending order.

1. Illustrate merge sort on $A_1=[5,3,20,1,8]$.
2. Give and justify its time and space complexities for an array of $n$ elements.
3. Compare merge sort for arrays and for linked lists in terms of computational complexity.
4. Give two advantages and one disadvantage of merge sort for arrays compared with quicksort for arrays.

题目描述

对升序归并排序回答下列问题。

1. 用 $A_1=[5,3,20,1,8]$ 说明归并排序过程。
2. 给出并说明对 $n$ 元素数组进行归并排序的时间、空间复杂度。
3. 从计算复杂度角度比较数组与链表上的归并排序。
4. 与数组上的快速排序相比，说明归并排序的两个优点和一个缺点。

Kai

Q.1

One valid split-and-merge trace is

                         [5, 3, 20, 1, 8]
                         /              \
                    [5, 3]          [20, 1, 8]
                    /   \            /       \
                  [5]   [3]        [20]     [1, 8]
                                               / \
                                             [1] [8]

merge: [5] + [3]       -> [3, 5]
merge: [1] + [8]       -> [1, 8]
merge: [20] + [1, 8]   -> [1, 8, 20]
merge: [3, 5] + [1, 8, 20]
                         -> [1, 3, 5, 8, 20]

Thus the sorted array is

$$\boxed{[1,3,5,8,20]}.$$

Q.2

At each recursion level, merging all subarrays costs $\Theta(n)$, and the recursion has $\lceil\log_2 n\rceil$ levels. Equivalently,

$$T(n)=2T(n/2)+\Theta(n)=\boxed{\Theta(n\log n)}$$

in the best, average, and worst cases.

For arrays, the merge buffer requires $\Theta(n)$ space. The recursion stack requires $\Theta(\log n)$ more, so the total auxiliary space is

$$\boxed{\Theta(n)}.$$

Q.3

Both implementations take $\Theta(n\log n)$ time.

• For an array, subarray boundaries are obtained in $O(1)$ time, but merging requires an auxiliary array of $\Theta(n)$ elements.
• For a linked list, splitting requires traversal, but the total work at each recursion level remains $\Theta(n)$. Merging can relink nodes and needs only $O(1)$ auxiliary space; a recursive implementation additionally uses a $\Theta(\log n)$ call stack. A bottom-up implementation can use $O(1)$ auxiliary space.

Q.4

Compared with quicksort on arrays, merge sort has the following advantages:

1. its worst-case running time is guaranteed to be $\Theta(n\log n)$, whereas ordinary quicksort can take $\Theta(n^2)$;
2. it is stable when equal keys are taken from the left subarray first, whereas ordinary in-place quicksort is not stable.

Its main disadvantage is that array merge sort needs $\Theta(n)$ auxiliary storage, while an in-place quicksort normally needs only its recursion stack.