Let $x \in \mathbb{R}^p$ denote a $p$ dimensional data point (a vector). I have two sets $A = \{x_1, .., x_n\}$ and $B = \{x_{n+1}, .., x_{n+m}\}$. So $|A| = n$, and $|B| = m$. Given $k \in \mathbb{N^*}$, let $d_x^{(A, k)}$ denote the mean Euclidean distance from $x$ to its $k$ nearest points in $A$; and $d_x^{(B, k)}$ denote the mean Euclidean distance from $x$ to its $k$ nearest points in $B$.

I have the following algorithm:

 - $A' = \{ x_i \in A \mid d_{x_i}^{A, k)} > d_{x_i}^{(B, k)} \}$ ... (1)
 - $A = A \setminus A'$ ... (2)
 - $B' = \{ x_i \in B \mid d_{x_i}^{A, k)} < d_{x_i}^{(B, k)}$ ... (3)
 - $B = B \setminus B'$ ... (4)
 - $A = A \cup B'$ ... (5)
 - $B = B \cup A'$  ... (6)
 - Repeat (1), (2), (3), (4), (5) and (6) until: (no element moves from $A$ to $B$ or from $B$ to $A$, that is A' and B' become empty) or (|A| $\leq$ k or |B| $\leq$ k)

Do this algorithm terminates, and if it so, is it possible to easily prove it ? Is it also possible to have an upper bound for the number of iterations required to terminate ?

**Note:** the $k$ nearest points to $x$ in a set $S$, means: the $k$ points (others than $x$) in $S$, having the smallest Euclidean distance to $x$.