# What is the mathematical proof behind this algorithm?

I have a question that is essentially asking me to find the minimum absolute value between the difference of pairs in two arrays.

If I have an array $A = [1, 3, 2, 4]$ and $B=[9,6,8,10]$, Then it would be best to sort both arrays A and B so that $A=[1,2,3,4]$ and $B=[6,8,9,10]$, then iterate through both arrays and calculate the absolute value of the difference between the numbers at each point. This will give you the minimum.

What I can't put into mathematical words is why. I can intuitively understand it, but I can't put it into words. Can someone explain why this is, mathematically?

However, consider $C=\{1,2,3,4\}$ and $D=\{9,6,8,10\}$ as sets. You want to find $\min\{|c-d|:c\in C, d\in D\}$. You can do that by first calculating all differences $\{|c-d|:c\in C, d\in D\}$ and then select the minimum.
Now what you algorithm does is the following: Given a particular order of $C$ and $D$ (your sorted arrays), it "builds" the set $\{|c-d|:c\in C, d\in D\}$ step by step (basically constructing sets $S_1$, $S_2$ etc. until $S_m=\{|c-d|:c\in C, d\in D\}$ for some $m$, where $S_i$ and $S_{i+1}$ only differ by one element) and at each step looks what the minimum of the newly constructed set is. But your algorithm is intelligent enough not to construct the sets explicitly in memory, but concentrates on the minimas. It uses that $\min (S_i\cup\{j\})=\min\{j,\min S_i\}$, so the algorithm only carries the current minimum $\min S_i$ and the index $i$ to know what it has checked and what still needs checking. You see that in the end, it gets $\min S_m = \min\{|c-d|:c\in C, d\in D\}$ (what we looked for).
You didn't specify in which way the arrays are iterated through, so I kept it general, but possibly you iterate through all elements of $A$ and in that loop through all elements of $B$. In that case, the number of sets implicitly constructed in the "background" (but not explicitly in the algorithm) is $m=4\cdot 4=16$.