find separate pairs of points with minimal total distance I am looking for suitable algorithm how to solve the following problem.

For finite set $S \subset \mathbb{R}$ ($|S| = N_{S}$) we need to find its disjunctive separation $S = A \cup B$ ($A \cap B = \emptyset$) on two ordered sets and assignment $\pi$ between elements of these two sets, where the following conditions must be fulfilled:


$|A| = |B| = N$ where $N = \lfloor N_s/2 \rfloor$
$s_k \in S$ where $k = 1,2, ...,N_s$ 
$a_i \in A$ and $b_j \in B$ where $i,j = 1,2, ..., N$
$\sum_{i=1}^{N}|a_{\pi(i)} - b_i| \to min$


In other words, I am looking for method how to find set of separated pairs $[a_{\pi(i)},b_i]$ assignments.

Example:
$$S = [3.0, 2.1, 0.9, 2.9, 1.1], N_s = 5, N = 2$$
then 
$$A = [3.0, 0.9]$$ 
and 
$$B = [2.9, 1.1]$$ which produce following separate pairs:

$$[3.0, 2.9], [0.9, 1.1]$$

Note: I am not sure if my problem description is sufficiently rigorous and clear. But I tried do my best.
Sort the items so that $s_1 \le s_2 \le \dots \le s_{N_S}$. Then: 


If $N_S$ is even, assign all the odd-numbered items to $A$, all even-numbered items to $B$, and pair the first item of $A$ with the first of $B$, etc. This assignment must be optimal, since any pairing in which two pairs overlap can always be transformed into a pairing with no overlap that does not cost more. 
If $N_S$ is odd, enumerate over all possible items $s_i$ in $S$ and for each of them, compute the best partition of $S \setminus \{s_i\}$, which is an even-size set, using the previous case. Return the best partition among all $N_S$ cases. 


The total cost of this procedure is $O(N_S \log N_S)$ when $N_S$ is even and $O(N_S^2 \log N_S)$ when $N_S$ is odd.