In a post from about a year ago, I explained an algorithm for counting the number of inversions of a sequence in $latex O(n \lg n)$ time. As a reminder, given a sequence $latex a_1, a_2, \dots, a_n…