Вывести количество пар, которые в неправильном порядке в массиве?(Java)

Question

Например, у меня есть массив

int IDs[]={1,21,5,3,12,23,2};

Количество пар в неправильном порядке 9, Пары: (21, 5) (21,3) (21, 12) (21,2) (5,3) (5,2) (3,2) (12,2) (23,2),

Итак, мой алгоритм для этого предполагает два для:

 for(int i=0;i<IDs.length;i++)
    {
        for(int j=i+1;j<IDs.length;j++)
        {
            if(IDs[i]>IDs[j]) 
                wrong++;             
        }
    }

Проблема в том, что это имеет сложность n^2, и я должен иметь сложность максимум n*log n.

Answer 1

Количество пар в неправильном порядке называется количеством инверсий. С этим знанием кто-то может легко найти предыдущее решение:
Подсчет инверсий в массиве