Question

Write an algorithm that sorts a lists of \(n\) items by dividing it into three sublists of about \(n / 3\) items, sorting each sublist recursively and merging the three sorted sublists. Analyze your algorithm, and give the results under order notation.

Short answer

The developed algorithm first divides the list into three sublists, sorts each using recursion, and then merges them. The analysis demonstrates that this three-way mergesort algorithm's time complexity is \(O(n*log(n))\) according to the Master's Theorem.

Step-by-step solution

Algorithm Design

Begin the designing of the algorithm. The algorithm should include splitting of the list into three equal parts, then recursively sort each part, and finally merge them back together. Here's a suggestion for the algorithm: 1. Check if length of list is less than or equal to 1, if so, the list is already sorted.2. Otherwise, divide the list into three roughly equal sublists.3. Sort each sublist by recursively applying this algorithm.4. Merge the three sorted sublists back into one.This is similar to merge sort, but with three sublists instead of two.

Algorithm Analysis

After designing the algorithm, it's time to perform an analysis of it with respect to time complexity.The time complexity T(n) of this three-way merge sort can be expressed with the recurrence relation T(n) = 3T(n / 3) + O(n). This is because the algorithm divides the problem into three sub-problems of size n / 3 (the three sublists), solves each in T(n / 3) time (recursively sorting the sublists), and then spends O(n) time to merge the sublists together.

Order Notation

To conclude the analysis, the results should be presented under order notation. According to the Master theorem, the solution to the recurrence T(n) = aT(n / b) + O(n^d) is T(n) = O(n^d * log^n) if a > b^d, T(n) = O(n^d) if a = b^d, and T(n) = O(n^(log_b a)) if a < b^d. Here, a = 3, b = 3, and d = 1, thus a = b^d. Therefore, by the Master theorem, this three-way merge sort algorithm has time complexity T(n) = O(n*log(n)).

Key concepts

Three-Way Merge Sort

Imagine dividing a list of numbers into three parts instead of the usual two in merge sort. This is the key idea behind the Three-Way Merge Sort. In this type of sort, the list is split into three roughly equal parts. Each of these parts, or sublists, is then sorted individually. This is done recursively, meaning each sublist will be split into three parts again, sorted, and merged. The process continues until each sublist contains at most one element. A single item or an empty list is inherently sorted by nature. Finally, the sorted sublists are merged back together, ultimately forming a fully sorted list. Three-Way Merge Sort can be a bit more complex due to the additional division. However, by following the above steps:

• Split the list into three parts.
• Sort each part recursively.
• Merge the sorted parts back together.

Ultimately, a sorted version of the original list is achieved, taking advantage of the classic divide and conquer strategy.

Recurrence Relation

A Recurrence Relation can be thought of as a mathematical way to express the time complexity of recursive algorithms. It helps us understand how the time required for the algorithm grows as the input size increases.For Three-Way Merge Sort, the recurrence relation can be expressed as:\[ T(n) = 3T(n / 3) + O(n) \]Here's what each part means:

• \(3T(n / 3)\): Represents the three sublists created, each requiring \(T(n / 3)\) time to sort.
• \(O(n)\): Represents the time taken to merge the sublists into a single sorted list.

Recurrence relations provide insight into how the algorithm performs based on its recursive nature, showing the cost of dividing the problem and combining the results.

Master Theorem

The Master Theorem is a powerful tool used to determine the running time of algorithms that follow a divide and conquer approach. By using this theorem, we can find the order of growth for such algorithms.The Master Theorem provides a straightforward formula:\[ T(n) = aT(n / b) + O(n^d) \]Where:

• \(a\) is the number of subproblems in the recursion.
• \(b\) is the factor by which the subproblem size is reduced.
• \(d\) is the polynomial order of the \(O(n^d)\) term that accounts for combining the solutions.

In the case of Three-Way Merge Sort:

• \(a = 3\): Three subproblems.
• \(b = 3\): Each subproblem is a third of the original size.
• \(d = 1\): Linear time is taken to merge the results.

According to the Master Theorem, since \(a = b^d\), the time complexity is:\[ T(n) = O(n \log(n)) \]

Time Complexity Analysis

Time Complexity Analysis is essential when evaluating how efficient an algorithm is, especially as input sizes grow. For Three-Way Merge Sort, the central question is how the steps of dividing, sorting, and merging affect overall growth.The recurrence relation for this sort provides a basis to evaluate time complexity as:\[ T(n) = 3T(n / 3) + O(n) \]Using the Master Theorem simplifies this to show the ordering of operations:

• The division into three parts drives logarithmic growth: \(\log(n)\).
• The linear merging operation: potentially touching every element once per merge.

Together, these factors suggest a time complexity of \(O(n \log(n))\).
This demonstrates Three-Way Merge Sort's efficiency, comparable to traditional merge sort for larger datasets. Understanding time complexity helps underline this algorithm's practicality among other sorting options.