Consider the following $"3-$way merge sort" algorithm that takes input

S $,$ a sequence of n elements, where $n=3^m($i$.$e$.,$ n is a power of $3)$ and

Merge $3$ is a procedure that takes $3$ sorted lists and merges them into

a sorted list.

Merge$3$Sort $($A$,$ n$)$

$\{$ if $($n $>1)$

$\{$ A$1\backslash$leftarrow leftmost n$/3$ items of A;

A$2\}\backslash$leftarrow$\backslash$mathrm$\{$ middle n$/3$ items of A;

A$3\backslash$leftarrow rightmost n$/3$ items of A;

Merge$3$Sort $($A$1,$ n$/3)$;

Merge$3$Sort $($A$2,$ n$/3)$;

Merge$3$Sort $($A$3,$ n$/3)$;

Merge$3($A$1,$ A$2,$ A$3)$;

$\}$

$\}$

Describe $($do not write code$)$ an algorithm for Merge$3,$ the $3$way$-$

merge procedure that takes three sorted lists and merge them into a

single sorted list.

What is the complexity of your Merge$3,$ the $3$way$-$merge

algorithm? Express it in terms of big$-$O notation.

Write the recurrence relation that describes the complexity of the

$3-$mergesort.