Comparing 1 million integers in an array without sorting it first

Question

I have a task to find the difference between every integer in an array of random numbers and return the lowest difference. A requirement is that the integers can be between 0 and int.maxvalue and that the array will contain 1 million integers.

I put some code together which works fine for a small amount of integers but it takes a long time (so long most of the time I give up waiting) to do a million. My code is below, but I'm looking for some insight on how I can improve performance.

for(int i = 0; i < _RandomIntegerArray.Count(); i++) {
  for(int ii = i + 1; ii < _RandomIntegerArray.Count(); ii++) {
    if (_RandomIntegerArray[i] == _RandomIntegerArray[ii]) continue;

    int currentDiff = Math.Abs(_RandomIntegerArray[i] - _RandomIntegerArray[ii]);

    if (currentDiff < lowestDiff) {
      Pairs.Clear();
    }

    if (currentDiff <= lowestDiff) {
      Pairs.Add(new NumberPair(_RandomIntegerArray[i], _RandomIntegerArray[ii]));
      lowestDiff = currentDiff;
    }
  }
}

Apologies to everyone that has pointed out that I don't sort; unfortunately sorting is not allowed.

Answer 1

Imagine that you have already found a pair of integers a and b from your random array such that a > b and a-b is the lowest among all possible pairs of integers in the array.

Does an integer c exist in the array such that a > c > b, i.e. c goes between a and b? Clearly, the answer is "no", because otherwise you'd pick the pair {a, c} or {c, b}.

This gives an answer to your problem: a and b must be next to each other in a sorted array. Sorting can be done in O(N*log N), and the search can be done in O(N) - an improvement over O(N²) algorithm that you have.