Crowdly
Add to Chrome
Recall merge sort: Sort(a[0..n-1]) RETURN MergeSort(a, 0, n-1) ...
✅ The verified answer to this question is available below. Our community-reviewed solutions help you understand the material better.
Recall merge sort:
Sort(a[0..n-1])RETURN MergeSort(a, 0, n-1)
MergeSort(a, lo, hi)IF lo >= hi
RETURN a[lo..hi]
mid ← (lo + hi + 1) DIV 2
l ← MergeSort(a, lo, mid-1)
r ← MergeSort(a, mid, hi)
RETURN Merge(l, r)
where DIV is division discarding any remainder to return a whole number.
Merge(l[0..q-1], r[0..s-1])m ← a new array of length q+s
i ← 0
j ← 0
WHILE i < q OR j < s
IF i < q AND (j = s OR l[i] <= r[j])
m[i+j] ← l[i]
i ← i+1
ELSE
m[i+j] ← r[j]
j ← j+1
RETURN m
Consider a merge sort of the following array:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 17 | 12 | 8 | 2 | 7 | 18 | 46 | 99 | 14 | 3 |
What values will be assigned to the variables l and r in the outermost call of MergeSort?