Question

There are n field stacks and the mass of i-th field stack is mi (mi > 0). Bob wants to merge
the n field stacks into only 1 stack. Every time Bob can merge one field stack with another
and the merging cost is the mass of two stacks. For example, there are 3 field stacks, and
their masses are m1 = 1, m2 = 2 and m3 = 4. You can merge m1 and m2 with the cost of
1 + 2 = 3, and then merge the new stack with m3, where the cost is 3 + 4 = 7, and the total
cost is 3 + 7 = 10.

Given the number of field stacks n and their masses mi, you should:

(a) Design a greedy algorithm to merge all field stacks with the lowest cost;
(b) Analyze the time complexity of your greedy algorithm;
(c) Prove the correctness of your algorithm;