前面一半数字中,3与后面1个数字（2）组成逆序,5与后面2个数字(42)组成逆序,…,(2n-1)与后面n-1个数字((2n-2)...42)组成逆序,所以前一半数字的逆序数是1+2+...+(n-1)=n(n-1)/2.
后面一半数字中,2n与后面n-1个数字（(2n-2)...42）组成逆序,2n-2与后面n-2个数字（(2n-4)...42）组成逆序,…,4与后面1个数字(2)组成逆序,所以后一半的逆序数是(n-1)+(n-2)+...+2+1=n(n-1)/2.
总逆序数是以上两部分相加为n(n-1).