If you sort the elements first, you can get the runtime down to
O(n log n).
The idea here is that if
a is the list of integers in
sorted order and
b[i] is the sum of the differences between
a[i] and the other numbers, then
b[i+1] can be
computed directly in terms of
a[i+1] - a[i], and the length of the array.
I won't say exactly how, but here's a hint. How much can
Math.abs(a[i+1] - a[j]) differ from
a[j])? For which
a[j]) greater? For which
j is it smaller?
Now, after you compute those, the
b[i]s then among
themselves contain each difference twice. The value you want is just their
sum divided by 2.