<aside> 💡

Topic 02: Divide and Conquer: Mergesort and Quicksort

Deadline: Oct. 25, 2024.

Team members: 5+5+10+5+6

</aside>

  1. Programming Assignment: Implement MERGE-SORT. Solution:

  2. Use Mergesort to sort the list $A$ below. Show the actions step by step. $A=[18, 11, 25, 16, 20, 13, 15, 30]$. Solution: (紙本)

  3. Write an algorithm MERGE-SORT3 that sorts a list of $n$ items by dividing it into three sublists of about $n/3$ items, sorting each sublist recursively and merging the three sorted sublists.

    1. Provide a pseudocode.
    2. Analyze your algorithm, and give the results under order notation.

    Solution: (紙本)

  4. Use Quicksort to sort the list $A$. Show the actions step by step. $A=[18, 11, 25, 16, 20, 13, 15, 30]$ Solution: (紙本)

  5. Stable sorting algorithms maintain the relative order of records with equal keys (i.e. values). That is, a sorting algorithm is stable if whenever there are two records $R$ and $S$ with the same key and with $R$ appearing before $S$ in the original list, $R$ will appear before $S$ in the sorted list. Determine whether Mergesort and Quicksort are stable. Solution: (紙本)