Эффективный способ подсчета количества перестановок для сортировки массива целых чисел в порядке возрастания

Учитывая массив значений длины n, есть ли способ подсчитать количество замен, которые будут выполнены сортировкой вставкой для сортировки этого массива по времени лучше, чем O (n ² )?

Например:

arr[]={2 ,1, 3, 1, 2};  // Answer is 4.

Алгоритм:

for i <- 2 to N

    j <- i

 while j > 1 and a[j] < a[j - 1]

       swap a[j] and a[j - 1]  //I want to count this   swaps?

       j <- j - 1