Question

a path is any sequence of edges that leads from the root to a leaf of a tree. The length of a path is the number of edges it traverses. So a path from A to B to C to D has length 3.

The questions refer to a simple optimization that can be done to improve the performance of mergesort. This is a modification to mergesort that performs the merge operation only if the last element of the first half of the array is greater than the first element of the second half of the array. Thus whenever the last element of the first half is less than or equal to the first element of the second half, we can avoid merging.

Suppose you draw the decision tree for mergesort when applied to an array of 2^k elements. What will be the exact length of the longest path in the tree? (Assume that the optimization for mergesort is not being used.)

Suppose you draw the decision tree for mergesort when applied to an array of 2^k elements. What will be the exact length of the shortest path in the tree?  (Assume that the optimization for mergesort is not being used.)

Suppose you draw the decision tree for mergesort when applied to an array of 2^k elements. What will be the exact length of the shortest path in the tree?  (Assume that the optimization for mergesort is being used.)

Answer 1

// optimization mergesort
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "iostream"

using namespace std;

int main()
{

int elem = 2000; // elements array #2k
int con = 0; // counter division elements
int path; // path counter
double div; // posible division

//1)-- LONGETS PATH without optimization

div = 2000; // inicial div = #elem
while ( div >= 1) // provided that div is greater than 1, the paths can continue to be divided
{
div = div/2;
con++;
}
path = con*2; // the number of longest path are the number of possible divisions by 2
// because it is the longest path that can be taken

cout<<"Longest Path: "<<path<<endl;

//2)-- SHORTEST PATH without optimization

// at some point an odd array remains, which avoids the division and union
// of an element, so those edges of the longest path(without optimization) are subtracted
path = con*2 - 2;

cout<<"Shortest Path: "<<path<<endl;

//3)-- SHORTEST PATH WITH OPTIMIZATION
// Since the array can be divided X times, it means that it can be merged X times.
// In the best case (shortest path) the optimization condition is met,
// and the merged is not necessary, so X times can be avoided,
// except at the last edge.
path = con + 1;
cout<<"Shortest Path with Optimization: "<<path<<endl;
}

COMMENT DOWN FOR ANY QUERIES AND,

LEAVE A THUMBS UP IF THIS ANSWER HELPS YOU.