Based off of timing test the below algorithm has N^2*logN complexity. But I dont understand why? And what is the difference between average case complexity and worse case complexity with this algorithm.

unsigned rnd(unsigned limit) { return rand() % limit; }

void permute (int a[], int n) { for (int i = 0; i

N Repititions Time NA2*logN TINA2 logN NA2 T/NA2 Nn3 Time/NA3 0.012 20000 0 0000006 10000 0 0000012 1000000 0.000000012 100 100 1E+09 1.031E-09 1000 100 1.031 3000000 3.43667E-07 1000000 1.031E-06 100 4.635 13204119.98 3.51027E-07 4000000 1.1588E-06 8E+09 5.79375E-10 2000 100 10.696 31294091.29 3.4179E-07 9000000 1.1884E-06 2.7E-10 3.96148E-10 3000 4000 100 18.908 57632959.86 3.280 E-07 16000000 1.1818E-06 6.4E-10 2.95438E-10 100 31.752 92474250.11 3.4336E-07 25000000 1.2701E-06 1.25E-11 2.54016E-10 5000 100 45.173 136013445 3.32122E-07 36000000 1.2548E-06 2.16E-11 2.09134E-10 6000 100 62.047 188409804 3.29319E-07 49000000 1.2663E-06 3.43E-11 1.80895E-10 7000 8000 100 82.105 249797759.2 3.28686 E-07 64000000 1.2829E-06 5.12E-11 1.60361E-10 20000 0.0000011 10000 0 0000022 1000000 0.000000022 0 200 0.022 100 200 2.065 3000000 6.88333E-07 1000000 065E-06 1E+09 2.065E-09 1000 200 8.69 13204119.98 6.58128E-07 4000000 2.1725E-06 8E+09 1.08625E-09 2000 3000 200 20.811 31294091.29 6.65014E-07 9000000 2.3123E-06 2.7E-10 7.70778E-10 4000 200 37.754 57632959.86 6.55077E-07 16000000 2.3596E-06 6.4E-100 5.89906E-10 200 62.874 92474250.11 6.799 E-07 25000000 2.515E-06 1.25E-11 5.02992E-10 5000 200 90.805 136013445 6.6761 -07 3600000000 2.5224E-06 2.16E+11 4.20394E-10 6000