Consider the use of the recursive MergeSort algorithm to sort a sequence of n elements.

Question

Consider the use of the recursive MergeSort algorithm to sort a sequence of n elements. Approximate the largest number of pushes (without corresponding pops) to the stack that will existing at any time during the execution of this algorithm. In other words, approximately how deep will the stack become as the MergeSort algorithm sorts an -element sequence? You must justify your answer.

THEORETICALLY ANSWER

 

Summary

Recursion occurs in each step of the merge sort algorithm, which uses a divide and conquers strategy.
For a series with ‘n’ elements, the depth of the stack would be log2(n).
There will be a total of (2*n – 1) pushes.

Explanation

Merge sort employs a divide-and-conquer strategy.
It divides the input array into two equal halves and calls itself for each half if the input sequence has n’ elements. This operation will be repeated until the sequence is atomic (that is, it contains only one element and cannot be divided further).

The Merge sort algorithm:

function merge_sort(arr[], l, r)

if r>l

Find the middle index to divide the given array into two equal halves.

Allocate memory for middle m= (l + (r-1))/2

Call the merge_sort function for the first half.

Call the function merge_sort(arr, l, m)

Call the merge_sort function for the second half.

Call the function merge_sort(arr, m+1, r)

Merge the results obtained after calling the two functions above.

Call the function merge(arr, l, m, r)

The merge sort function is called recursively twice in each call in the aforementioned method, and then the merge function is invoked to merge the separated sub-arrays.

The merge sort technique is seen in the image above applied to an 8-number sequence.

As previously stated, after pushing the initial merge sort function call into the stack, each pop action will be followed by two push operations until the function’s base condition is reached. If the left and right indices in a popped function call are equal, the base condition is met, and no push occurs.

Height = log2 n

Depth of stack = log2 n

no. of pushes in total =

= 2°+2¹+2²+—–2ⁿ

=2°+2¹+2²+—–2^logn₂

=(2^logn+1_2)-1

=2.2^logn_2-1

=2n-1

 

Also, read check the python code below that doesn’t work properly, adjust it, and explain?