Mergesort is a perfect example of a successful application of the divide-and-conquer technique. It sorts a given array A[0..n − 1] by dividing it into two halves A[0.. n/2 − 1] and A[ n/2 ..n − 1], sorting each of them recursively, and then merging the two smaller sorted arrays into a single sorted one.

**Mergesort**

Mergesort
is a perfect example of a successful application of the divide-and-conquer
technique. It sorts a given array ** A**[0

**ALGORITHM** *Mergesort*** (A**[0

//Sorts
array *A*[0** ..n** − 1] by recursive mergesort
//Input: An array

//Output:
Array *A*[0** ..n** − 1] sorted in nondecreasing order

**if ***n >*** **1

copy ** A**[0

*Mergesort*** (B**[0

*Mergesort*** (C**[0

*Merge**(**B, C, A*** )** //see below

The ** merging**
of two sorted arrays can be done as follows. Two pointers (array indices) are
initialized to point to the first elements of the arrays being merged. The
elements pointed to are compared, and the smaller of them is added to a new
array being constructed; after that, the index of the smaller element is
incremented to point to its immediate successor in the array it was copied
from. This operation is repeated until one of the two given arrays is
exhausted, and then the remaining elements of the other array are copied to the
end of the new array.

**ALGORITHM** *Merge*** (B**[0

//Merges
two sorted arrays into one sorted array //Input: Arrays ** B**[0

//Output:
Sorted array ** A**[0

**while ***i < p*** and ***j < q*** do if **** B**[

** A**[

**if ***i*** **=** ***p*

copy ** C**[

The
operation of the algorithm on the list 8** ,** 3

How
efficient is mergesort? Assuming for simplicity that ** n** is a power of 2, the recurrence
relation for the number of key comparisons

Let us
analyze ** C_{merge}(n),** the
number of key comparisons performed during the merging stage. At each step,
exactly one comparison is made, after which the total number of elements in the
two arrays still needing to be processed is reduced by 1. In the worst case,
neither of the two arrays becomes empty before the other one contains just one
element (e.g., smaller elements may come from the alternating arrays).
Therefore, for the worst case,

Hence,
according to the Master Theorem, *C _{worst}*

** C_{worst} (n) **=

The
number of key comparisons made by mergesort in the worst case comes very close
to the theoretical minimum^{2} that any general comparison-based
sorting algorithm can have. For large ** n,** the
number of comparisons made by this algo-rithm in the average case turns out to
be about 0

There are
two main ideas leading to several variations of mergesort. First, the algorithm
can be implemented bottom up by merging pairs of the array’s elements, then
merging the sorted pairs, and so on. (If ** n** is not a
power of 2, only slight bookkeeping complications arise.) This avoids the time
and space overhead of using a stack to handle recursive calls. Second, we can
divide a list to be sorted in more than two parts, sort each recursively, and
then merge them together. This scheme, which is particularly useful for sorting
files residing on secondary memory devices, is called

**Exercises
5.1**

1. **a. **Write pseudocode for a
divide-and-conquer algorithm for finding the po-sition of the largest element
in an array of ** n** numbers.

1. b. **
**What will be your algorithm’s output for arrays
with several elements of the largest value?

** **c. Set up and solve a recurrence relation for the
number of key comparisons made by your algorithm.

** **d. How does this algorithm compare with the
brute-force algorithm for this problem?

** **2. **a. **Write
pseudocode for a divide-and-conquer algorithm for finding values** **of both the largest and smallest
elements in an array of ** n** numbers.

** **b. Set up and solve (for ** n** = 2

** **c. How does this algorithm compare with the
brute-force algorithm for this problem?

** **3. **a. **Write
pseudocode for a divide-and-conquer algorithm for the exponenti-ation problem
of computing ** a^{n}** where

** **b. Set up and solve a recurrence relation for the
number of multiplications made by this algorithm.

** **c. How does this algorithm compare with the
brute-force algorithm for this problem?

** **d. As mentioned in Chapter 2, logarithm bases are
irrelevant in most contexts arising in analyzing an algorithm’s efficiency
class. Is this true for both asser-tions of the Master Theorem that include
logarithms?

1. Find the order of growth for solutions of the following recurrences.

**
**** T (n) **=

**
**** T (n) **=

**
**** T (n) **=

** **6. Apply mergesort to sort the list *E, X, A, M, P, L, E* in alphabetical
order.

** **7. Is mergesort a stable sorting algorithm?

** **8. **a. **Solve the
recurrence relation for the number of key comparisons made by** **mergesort in the worst case. You may
assume that ** n** = 2

** **b. Set up a recurrence relation for the number of key
comparisons made by mergesort on best-case inputs and solve it for ** n** = 2

** **c. Set up a recurrence relation for the number of key
moves made by the version of mergesort given in Section 5.1** .** Does taking the number of key
moves into account change the algorithm’s efficiency class?

** **9. Let ** A**[0

10. ** **Implement the bottom-up version of mergesort in the language of your choice.

11. *Tromino puzzle *A tromino (more accurately, a
right tromino) is an L-shaped* *tile
formed by three 1 × 1
squares. The problem is to cover any 2**^{n}** × 2

Design a
divide-and-conquer algorithm for this problem.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Introduction to the Design and Analysis of Algorithms : Divide and Conquer : Mergesort |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2023 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.