1) merge3sort program is given http://www.cs.rpi.edu/~moorthy/Courses/CSCI2300/lab3-2015-Dir/merge3sort.cc
  
2) Maximum Subarray solution is given here http://www.cs.rpi.edu/~moorthy/Courses/CSCI2300/lab3-2015-Dir/maxsubarray.cc

3) T(n) =2 *T(n/2) +1, T(2) =1

Let n= 2^k

Let Q(k) = T(2^k))

Q(k) = 2*Q(k-1) + 1

Q(1) - 1
Q(2) = 3
Q(3) = 7

Guess: Q(k) = 2 ^k -1 
 
Check:  2 ^k -1 = 2 *( 2*(k-1) -1) + 1

mateches.

Hence:
T(n)  = n -1

Optional: 
Like the previous exercise, we can write
Q(k) = 4*Q(k-1) +1
Q(1)=1
Q(2)=4*1+1=5
Q(3)=4*5+1=4^2+4+1=21

Q(k) = 4^{k-1}+4^{k-2}+4^{k-3} + ... + 1
     = 4^{k-1}+ (4^{k-1}-1)/3
     = 4^{k-1} * 4/3 - 1/3
     = 4^k/3 -1/3
T(n) = n^2/3 -1/3

From Masters Theorem: T(n) = a * T(n/b) + n ^d

here a = 4, b = 2, d = 0, ration a/b^d > 1

Hence the answer is O(n^log_2(4)) which is O(n^2)