Mergesort3: your friend suggests the following variation of mergesort: instead of splitting the list into two halves, we split it into three thirds. then we recursively sort each third and merge them. mergesort3 (): if n < = 1, then return a[1..n] let k = n/3 and m = 2n/3 mergesort3(a[1..k]) mergesort3(a[k+1..m]) mergesort3(a[m+1..n)merge3(a[1..k], a[k+, a[m+1..n])return a[1..m].merge3(l0, l1, l2): return merge(l0, merge(l1, that you have a function merge that merges two sorted lists of lengths q and p in time k(q+p) where k is a constant. you may assume that n is a power of 3, if you wish.(a) what is the asymptotic running time for executing merge3(l0, l1, l2), if l0, l1, l2 are three sorted lists of length n/3? give the tightest bound possible. show your work! (b) let t(n) denote the running time of mergesort3 on an array of size n. write a recurrence relation for t(n) and solve it using the tightest bounds possible.(c) compare the running time of mergesort3 to the running time of ordinary mergesort.