JavaScript Question

In merge sort, which uses a divide-and-conquer approach to sortan array of values. There are many more algorithms that takes suchan approach. Implement a function that computes the sum of an arrayof integers using divide and conquer. The function should have thefollowing signature:

function divideAndConquerSum(a);

where a is the array. The recursive calls sum up the numbers inthe base case, and ?merges? the sums of the recursive callsotherwise. For example, the return value for the array a=[1,5,-1,4] is 9.To make it a bit more interesting, instead ofsplitting into two sub-arrays like in merge sort, I want you tosplit into three sub-arrays at each divide step. Submit yourcomplete code, including a function that demonstrates that yourimplementation works with a few test inputs .Hint: Like in theimplementation of merge sort, you may need a helper function thatdoes the actual recursion.

2 Runtime Analysis (Theory part)

What is the runtime of the algorithm that you implemented?Provide a recurrence relation forT(n) according to this concept formerge sort (you can ignore constant1

factors)

and solve it . Give the final ? complexity . Describe yourreasoning briefly with stepwise.

Mergesort Running Time. 1. If the array has 0 or 1 elements, it's sorted. Stop. 2. Split the array into two approximately equal-sized halves. 3. Sort each half recursively (using Mergesort). 4. Merge the sorted halves to produce one sorted result: Consider the two halves to be queues. T(1) = 1 1 2T (n/2) n Repeatedly dequeue the smaller of the two front elements (or dequeue the only front element if one queue is empty) and add it to the result. 21