A furniture store is having a sale: purchase two items at the price of the more expensive one. John, having just moved to a new house, rushed into the store and chose $2k$ items of furniture, $f_1, f_2, \dots, f_{2k}$. The items are priced $p_1, p_2, \dots, p_{2k}$, respectively. Help John arrange the items in pairs so that the overall cost of the $2k$ items is minimal. Suggest an algorithm that runs in time $O(k\log k)$ and prove its correctness and running time.
Ok, so it sounds not too complicated: first, I will sort all the $2k$ items by their prices to array, and then each cell and his next are one couple. This takes time $O(k\log k)$.
How can I prove the correctness of what I suggest? I thought about assuming that there is a cheaper solution to get a contradiction but I dont know how to prove this.