Find the number of operations needed to sort [Solution found]

We are given an array A of distinct integers that is not necessarily sorted. To sort the array, we are only allowed to do the below operation.

Find the number of these operations needed to sort any given array A of size n. Here n lies between 1 and 10000.

We have to pick the smallest possible index i in A such that there exists an index j and j>i and A[j]<A[i]. For that picked smallest i, if there are multiple valid j, pick the smallest possible j. Then swap the picked i and j.

Applying the given operations, below is the states of the array at each operation.
So, the operations needed to sort {3,5,2,1,4} are 6.

P.S. - I was able to come up with an O(n^2) solution. Is there a better time complexity to solve this problem?

Was able to find an O(nlogn) solution.

1 Like

@vijju123, @taran_1407
Please provide your thoughts in this if you can spare some time. Thanks in advance.

1 Like

Spoiler Warning - Below is the observation that leads to an O(nlogn) solution. Can refer to it if you want to.

Click to View Hint

Each operation reduces the number of inversions by one.

1 Like