Tree method…
Nathan Sprague
private static void mergeSort(int[] numbers, int start, int end) {
if (start < end) {
int mid = (start + end) / 2;
mergeSort(numbers, start, mid);
mergeSort(numbers, mid + 1, end);
merge(numbers, start, mid, end);
}
}Socrative… Given that merge requires \(f(n)\) comparisons to merge \(n\) elements, provide a recurrence relation describing the worst-case number of comparisons performed by mergesort.
private static void merge(int[] numbers, int start, int mid, int end) {
int mergedSize = end - start + 1; // Size of merged partition
int[] mergedNumbers = new int[mergedSize]; // Dynamically allocate temporary
// array for merged numbers
int mergePos = 0; // Position to insert merged number
int leftPos = start; // Initialize left partition position
int rightPos = mid + 1; // Initialize right partition position
while (leftPos <= mid && rightPos <= end) {
if (numbers[leftPos] <= numbers[rightPos]) {
mergedNumbers[mergePos] = numbers[leftPos];
leftPos++;
}
else {
mergedNumbers[mergePos] = numbers[rightPos];
rightPos++;
}
mergePos++;
}
while (leftPos <= mid) {
mergedNumbers[mergePos] = numbers[leftPos];
leftPos++;
mergePos++;
}
while (rightPos <= end) {
mergedNumbers[mergePos] = numbers[rightPos];
rightPos++;
mergePos++;
}
// Copy merged numbers back to numbers
for (mergePos = 0; mergePos < mergedSize; mergePos++) {
numbers[start + mergePos] = mergedNumbers[mergePos];
}
}Socrative… How many comparisons (between keys) are performed by merge in the worst case?
\(W(1) = 0\)
\(W(n) = n - 1 + 2W(\frac{n}{2})\)
Now we can write down the overall sum: \[\sum_{j=0}^i n - 2^j \]
\(i\) is determined by the initial condition…
\(n/2^i = 1\)
\(i = \log_2 n\)
Substituting: \(\sum_{j=0}^{\log_2 n} n - 2^j\)
Useful fact: \(\sum_{j=0}^{n} 2^j = 2^{n+1} - 1\)
\[\sum_{j=0}^{\log_2 n} n - 2^j \] \[ = \sum_{j=0}^{\log_2 n} n - \sum_{j=0}^{\log_2 n} 2^j \] \[ = n (\log_2 n + 1) - \sum_{j=0}^{\log_2 n} 2^j \] (Apply useful fact.) \[ = n (\log_2 n + 1) - (2^{\log_2 n + 1} - 1) \] \[ = n \log_2 n + n - (2n - 1)\] \[ = n \log_2 n - n + 1 \]
Repeat the analysis for assignments…