Tree method…
Nathan Sprague
10/6/2021
private static void mergesort(int[] items, int[] temp,
int left, int right) {
if (left == right) {
return;
}
int mid = (left + right) / 2;
mergesort(items, temp, left, mid);
mergesort(items, temp, mid + 1, right);
merge(items, temp, left, mid, right);
}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[] items, int[] temp,
int left, int mid, int right) {
for (int i = left; i <= right; i++) {
temp[i] = items[i];// Copy subarray to temp
}
int i1 = left;
int i2 = mid + 1;
for (int curr = left; curr <= right; curr++) {
if (i1 == mid + 1) { // Left subarray exhausted
items[curr] = temp[i2++];
} else if (i2 > right) { // Right subarray exhausted
items[curr] = temp[i1++];
} else if (temp[i1] <= temp[i2]) { // Get smaller value (COUNT THIS!)
items[curr] = temp[i1++];
} else {
items[curr] = temp[i2++];
}
}
}
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…