java - 高度な挿入ソートを実装しながら時間の複雑さに苦戦

Question

挿入ソートが配列のソートを完了するのに必要なシフト（またはスワップ）の数を直接カウントする高度な挿入ソートを実装しています。この実装により、単一の入力で複数のテストケースに合格できるようになりました。実装しましたしかし、まだ時間の複雑さに苦しんでおり、最善の解決策を模索しています。

これが私のプログラムです。

public class Solution {

    public static void main(String[] args) {

        Scanner in = new Scanner(System.in);
           int T = in.nextInt();
           int[][] ar = new int[T][];
           for(int i=0;i<T;i++){
               int columnSize;
               columnSize = in.nextInt();
               ar[i] = new int[columnSize];
           for(int j=0;j<ar[i].length;j++)
               {
               ar[i][j]=in.nextInt(); 
               }
           }

        int starttTime = (int) System.currentTimeMillis();
        for(int i=0;i<T;i++)
        {   int count=0,i1,k;

            for(int j=1;j<ar[i].length;j++)
            {
                k=ar[i][j];
                for(i1=j-1; i1>=0 && k<ar[i][i1]; i1--)
                {ar[i][i1+1]=ar[i][i1];
                 count++; }
                ar[i][i1+1]=k;

            }
        System.out.println(count);

        }
        int endTime = (int) System.currentTimeMillis();
        System.out.println(endTime - starttTime);
    }
}