Sorting Algorithms: Mergesort and Quicksort

Mergesort Algorithm Overview and Procedural Steps

• Definition of Mergesort: Mergesort is a recursive sorting algorithm that follows the divide-and-conquer paradigm. It divides a list into halves, sorts them, and then merges the sorted halves back together.
• The Five Steps of the Mergesort Algorithm:     1. Divide: Divide the list in half evenly.     2. Base Case: If the portion of the list to be sorted contains fewer than two items (n < 2), simply return as it is already sorted.     3. Recursive Call (First Half): Call Mergesort recursively to sort the first half of the list.     4. Recursive Call (Second Half): Call Mergesort recursively to sort the second half of the list.     5. Merge: Merge the two resulting sorted sublists into a single sorted list.
• Implementation Parameters:     * The recursive mergesort method typically accepts three arguments:         1. The data array (the list to be sorted).         2. The left index (the starting point of the portion to be sorted).         3. The number of elements to sort ($n$).     * Initial Call: To sort an entire array, the initial call would be mergesort(data, 0, data.length).
• Handling Uneven Splits: If the list does not divide perfectly evenly, the second recursive call usually receives the extra element. The choice is arbitrary, but consistently giving the extra element to one side is necessary for the implementation.
• Merge Optimization (Check for Pre-Sorted Data):     * An optimization not included in some textbooks involves a "quick check" after the recursive calls but before the merge.     * If the largest item in the first half of the list is less than or equal to ($\le$) the smallest item in the second half, the list is already sorted, and the merge step can be skipped.     * This improves performance significantly for data that is already sorted.
• Memory and Efficiency Considerations:     * Standard implementations use a non-recursive merge method that utilizes a temporary array to store merged elements.     * After merging into the temporary array, the elements are copied back to the original array.     * While copying appears inefficient, it does not increase the asymptotic complexity ($Big-Oh$) of the merge portion.

Procedural Logic for the Merge Method

• Parameters of the Merge Method:     1. The data array.     2. The index where the first half begins.     3. The number of elements in the first half ($n1$).     4. The number of elements in the second half ($n2$).
• Index Management: The process maintains three distinct indices to track the progress through the two sublists and the temporary array.
• Comparison Logic:     * As long as both sublists contain elements, the values at the current indices of the sorted sublists are compared.     * The smaller value is placed into the next available position in the temporary array.
• Termination of the While Loop: The primary comparison loop terminates when one of the sublists becomes empty.
• Post-Comparison Copying:     * If the first list still contains elements after the loop, these remaining elements must be copied into the temporary array.     * If the second list still contains elements, they do not need to be copied into the temporary array because they are already located in their correct final positions within the original data array.
• Final Copy-Back: The elements in the temporary array are copied back into the original array. Only the specific elements processed during the current recursive call should be copied.
• Non-Recursive Wrapper: An overloaded non-recursive method is often provided to simplify the API for the user:     * public static <T extends Comparable<? super T>> void mergesort(T[] data)     * Inside this method, it calls the recursive version: mergesort(data, 0, data.length);.

Complexity Analysis and Mathematical Foundations of Mergesort

• Divide-and-Conquer Classification: Mergesort is a divide-and-conquer algorithm. It divides work into smaller subproblems of the same type, solves them via recursion, and combines results.
• Informal Analysis (Recursion Tree):     * At each level of the recursion tree, approximately all $n$ elements are involved in a merge process.     * The work performed at each level is $O(n)$.     * The number of levels in the recursion tree for an array of size $n$ is $\log_2(n)$.     * Total complexity (Level work $\times$ Number of levels) is $O(n imes ext{levels}) = O(n imes ext{log}_2(n))$.     * Note: The number of levels remains the same in both the best-case and worst-case scenarios.
• Mathematical Function Review Exercises:     * Given $T(n) = n^2 + ext{sqrt}(n)$:         * $T(4) = 4^2 + ext{sqrt}(4) = 16 + 2 = 18$         * $T(x) = x^2 + ext{sqrt}(x)$         * $T(\frac{n}{2}) = (\frac{n^2}{4}) + ext{sqrt}(\frac{n}{2})$     * Given recursive $T(1) = 1$ and $T(n) = 3 imes T(\frac{n}{2}) + n^2$ for n > 1:         * $T(2) = 3 imes T(1) + 2^2 = 3 imes 1 + 4 = 7$         * $T(x) = 3T(\frac{x}{2}) + x^2$         * $T(\frac{n}{2}) = 3T(\frac{n}{4}) + (\frac{n^2}{4})$
• Formal Recurrence Equation for Mergesort:     * Tasks involved:         1. Divide list in half ($O(1)$ for arrays, though not for linked lists).         2. Recursively sort $n/2$ items ($T(\frac{n}{2})$).         3. Recursively sort another $n/2$ items ($T(\frac{n}{2})$).         4. Merge items ($O(n)$).     * Equation: $T(n) = 2T(\frac{n}{2}) + n$
• Solving the Mergesort Recurrence:     * Step 1: $T(n) = 2T(\frac{n}{2}) + n$     * Step 2 (Substitute $T(\frac{n}{2})$): $T(n) = 2(2T(\frac{n}{4}) + \frac{n}{2}) + n = 4T(\frac{n}{4}) + 2n$     * Step 3 (Substitute $T(\frac{n}{4})$): $T(n) = 4(2T(\frac{n}{8}) + \frac{n}{4}) + 2n = 8T(\frac{n}{8}) + 3n$     * Step $k$ Pattern: $T(n) = 2^k T(\frac{n}{2^k}) + kn$     * Reaching the Base Case: The recursion stops when the data size is $1$, so $2^k = n$, which means $k = ext{log}_2(n)$.     * Final Result: $T(n) = n imes T(1) + n imes ext{log}_2(n)$. Since $n imes ext{log}_2(n)$ grows faster than $n imes ext{constant}$, the complexity is $O(n ext{log } n)$.
• General Formula for Recursive Algorithms: $T(n) = ext{cost of dividing} + ext{cost of recursion} + ext{cost of combining}$.

Quicksort Algorithm Principles

• General Quicksort Algorithm:     1. Pivot Selection: Select an element that approximates the median of the current array portion, designated as its "pivot."     2. Partitioning: Rearrange the array so that elements less than or equal to ($\le$) the pivot are on the left, and elements greater than or equal to ($\ge$) the pivot are on the right.     3. Place Pivot: Position the pivot in its final sorted location (where everything to its left is $\le$ pivot and everything to its right is $\ge$ pivot).     4. Recursive Sort (Left): Sort the sub-array to the left of the pivot.     5. Recursive Sort (Right): Sort the sub-array to the right of the pivot.
• Quicksort Implementation Notes:     * Arguments: The array, the first index, and the total size n.     * Base Cases:         * Standard: If array size is less than two (n < 2), return.         * Optimization: If size equals two ($n = 2$), swap elements if they are out of order and then return.         * Broader Base Case: Some implementations switch to Insertion Sort or other simple sorts when the subarray size falls below a threshold (e.g., $10$ to $15$ items).     * Handling Duplicates: It is best practice to allow duplicate values to go to either side of the pivot for better performance with widespread duplicates.

Partitioning and Pivot Selection in Quicksort

• Pivot Selection Strategy (MedianOf3):     * The goal is to select a pivot that is close to the actual median for a balanced split.     * Simple Choice: Using the first element. This is poor for already sorted arrays ($O(n^2)$).     * MedianOf3 Algorithm: Identify the first, middle, and last elements of the portion to be sorted. Sort these three elements relative to each other and choose the middle one as the pivot.
• Partitioning Mechanics:     * Hiding the Pivot: Once the pivot is selected via MedianOf3, it is swapped with the element at the index last - 1 (the second to last position) to keep it out of the way during partitioning.     * Main Scanning Loop:         * Initialize tooBigIndex at first + 1.         * Initialize tooSmallIndex at last - 2.         * tooBigIndex scans upward from the left until an element $\ge$ pivot is found.         * tooSmallIndex scans downward from the right until an element $\le$ pivot is found.         * If the indices have not crossed, swap the values at tooBigIndex and tooSmallIndex and continue.         * If the indices cross, the loop breaks.     * Restoring the Pivot: After the scanning loop, the pivot (stored at last - 1) is swapped with the element at tooBigIndex. The tooBigIndex is then returned as the location where the pivot ended up.

Complexity and Performance Comparison

• Complexity Benchmarks:     * Choosing the pivot (MedianOf3): $O(1)$.     * Handling the base case: $O(1)$.     * The partition method: Although it contains nested loops, it scans each element exactly once, making it $O(n)$.
• Total Complexity (Optimal Case):     * If the array splits equally: $T(n) = O(1) + O(n) + 2T(\frac{n}{2})$.     * This recurrence is identical to Mergesort, resulting in $O(n ext{log } n)$.
• Total Complexity (Worst Case):     * If the array splits poorly (e.g., one side always has size $n - 1$ and the other is a base case):     * $T(n) = O(1) + O(n) + O(1) + T(n-1)$.     * Solving this: $T(n) = T(n-1) + n = T(n-k) + ext{sum of terms from } (n-k) ext{ to } n$.     * The result is approximately the sum of integers from $1$ to $n$, which is $O(n^2)$.
• Average Case: Statistical analysis shows that on average Quicksort performs at $O(n ext{log } n)$.
• Practical Performance:     * Despite the theoretical $O(n^2)$ worst-case, Quicksort typically outperforms Mergesort in real-world scenarios.     * Using the medianOf3 strategy makes it remarkably difficult to find data that triggers the $O(n^2)$ behavior, even if the array is initially sorted or reversed.
• API Wrapper: Like Mergesort, Quicksort uses a non-recursive wrapper to hide implementation details:     * static void quicksort(Object[] arr) { quicksort(arr, 0, arr.length); }