Answered: The Algorithm Mergesort, calls the…

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Concept explainers

Question

The Algorithm Mergesort, calls the Algorithm Merge.

i) Determine the number of comparisons required by Algorithm Merge to merge the arrays A = [12, 15, 26, 29,
36] and B = [2, 5, 14, 25, 35, 47, 49]
(ii) Perform a desk trace of the algorithm Merge to show how the arrays A and B are
combined.
(iii) The computational complexity for Algorithm Merge is O(n) in the worst case.
Explain how this was obtained.
(iv) Let C(n) be the number of key comparisons required to execute Algorithm Mergesort
on a list of n elements. Write a recurrence relation for the number of comparisons
made by the algorithm in the worst case. Explain how each term is obtained.

ALGORITHM Merge(B[0..p- 1], C[0..q - 1], A[0..p+q-1])
//Merges two sorted arrays into one sorted array
//Input: Arrays B[0..p - 1] and C[0..q - 1] both sorted
//Output: Sorted array A[0..p+q - 1] of the elements of B and C
i←0; j←0; k ←0
while i < p and j <q do
if B[i] ≤ C[j]
A[k]← B[i]; i←i+1
else A[k]C[j]; j←j+1
k+k+1
if i = p
copy C[j..q - 1] to A[k..p+q - 1]
else copy B[i..p - 1] to A[k..p+q − 1]

Mergesort Algorithm
ALGORITHM Mergesort(A[0..n – 1])
//Sorts array A[0..n - 1] by recursive mergesort
//Input: An array A[0..n - 1] of orderable elements
//Output: Array A[0..n - 1] sorted in nondecreasing order
if n > 1
copy A[0..[n/2] - 1] to B[0..[n/2] - 1]
copy A[[n/2]..n - 1] to C[0.. [n/2] - 1]
Mergesort (B[0..[n/2] - 1])
Mergesort (C[0..[n/21 - 1])
Merge(B, C, A) //see below

Expert Solution

Step by step

Solved in 5 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions