# Inversion array of a given array

Let A[1...n] be an array of n distinct numbers. The ordering of the numbers is any permutation of [1,2,...,n]. An array Inv_A is defined as follows: Inv_A[i] = number of elements A[j] such that j<i and A[j] > A[i]. Give an optimal algorithm that computes the above array Inv_A. For example if A = [3,1,4,5,2] then Inv_A = [0,1,0,0,3]. Expected time complexity is O(nlogn).

• What have you tried? Hint 1: try altering merge sort to compute the thing. Hint 2: or try using segment trees to compute the thing. Aug 9, 2022 at 18:39
Apply heap-sort for in-place sorting in $$O(log(n))$$ time. For a real application, it's better to use the simple randomized-quick-sort. You can get enough build-in routines in almost every popular language.