Greedy algorithm proof

There are 2n product and their prices: P={p_1, p_2, ..., p_2n}.
When we buy the products in pairs we get the product with lower price for free.

I'm trying to prove formally that the following algorithm results in optimal solution:

• Sort P from high to low.

• Return the sorted prices as pairs.

This solution is pretty straightforward, however I'm having extremely difficult time proving it formally.

Let's assume that optimal answer is $A = \{(free_1, paid_1), ..., (free_n, paid_n)\}$ where $\forall i: free_i \le paid_i$, also sort this pairs by $paid$, i.e. $paid_1 \le paid_2 \le ... \le paid_n$.

I will use pairs to show products grouping - 1st product in pair I get for free, and for 2nd I need to pay.

If there is such $i$ that $paid_{i-1} > free_i$, take 2 pairs
$(free_{i-1}, paid_{i-1}), (free_i, paid_i)$ (in this case we need to pay $paid_{i-1} + paid_{i}$) and swap prices:

• In case $free_{i-1} \le free_i$ we got $(free_{i-1}, free_i), (paid_{i-1}, paid_i)$ (need to pay $free_i + paid_i$);

• In case $free_{i-1} > free_i$ we got $(free_{i}, free_{i-1}), (paid_{i-1}, paid_i)$ (need to pay $free_{i-1} + paid_i$).

In both cases we don't do solution worse (we can not improve solution because we suppose that $A$ is optimal, but there is case that after swapping solution will not changed, e.g. $free_i

• $\forall i: paid_{i-1} \le free_i \le paid_i$ (more intuition: in sequence from p.1 we insert $free_i$ on appropriate places), that gives sorted sequence: $\{free_1, paid_1, free_2, paid_2, ..., free_n, paid_n\}$

So we show that optimal answer can be expressed in form of sorted array.

StackExchange Computer Science Q#45272, answer score: 3