write efficient algorithm

Question

Let S be a set of n positive integers, where n is even. Give an efficient
algorithm to partition S into two subsets S1 and S2 of n/2 elements each
with the property that the difference between the sum of the elements
in S1 and the sum of the elements in S2 is maximum. What is the time
complexity of your algorithm?

Answer 1

When the difference is needed to be maximum, we will subtract larger element with smaller one.

Here also follow the same rule i.e. place all n/2 smaller elements in set S1 and remaining n/2 elements in set S2.

For this we need to do sorting: Quick sort algorithm can be applied which takes O(nlogn) time.

Then 1st n/2 elements will be placed in set S1 and remaining n/2 elements will be place in set S2.

Calculating difference takes constant time i.e. O(1).

therefore total time needed is O(nlogn)