Find the sum of closest distances For this task your code should take two sorted arrays of integers X and Y as input.  It should compute the sum of the absolute distances between each integer in X and its closest number in Y. 

Examples:

X = (1 5,9)
Y = (3,4,7)


The distance is 2 + 1 + 2.

X = (1,2,3)
Y = (0,8)


The distance is 1 + 2 + 3.

Your code can take input in any way that is convenient.

The main restriction is that your code must run in linear time in the sum of the length of the two arrays.. (You can assume that adding two integers takes constant time.)
Haskell, 70 64 bytes



a%b=abs$a-b
x@(a:b)#y@(c:d)|e:_&lt;-d,a%c&gt;a%e=x#d|1&gt;0=a%c+b#y
_#_=0


Try it online!

Explanation

First we define (%) to be the absolute difference between two numbers.  Then we define (#) to be the interesting function. In the first line we match when both lists are non-empty:

x@(a:b)#(c:d:e)


On our first case from here we bind d to e:_ with e:_&lt;-d.  This ensures that d is non-empty and sets it's first element to e.

Then if the second element of \$Y\$ (e) is closer than the first (c) to the first element of \$X\$ (a), we return x#d removing the first element of \$Y\$ and calling again with the same \$X\$.

If we match the pattern but don't pass the condition we do:

a%c+b#y


Which, removes the first item of \$X\$ and adds the absolute difference of it from the first element of \$X\$ to the remaining result.

Lastly if we don't match the pattern we return \$0\$.  Not matching the pattern means that \$X\$ must be empty because \$Y\$ cannot be empty.

This algorithm has order notation \$O(|X|+|Y|)\$.

Haskell, 34 bytes

Here's how I would do it in \$O(\left|X\right|\times\left|Y\right|)\$ time:



x#y=sum[minimum$abs.(z-)&lt;$&gt;y|z&lt;-x]


Try it online!