Number of lexicographical swaps to make the array non decreasing

Question

• A lexicographical swap is defined as:
  At each step, pick the earliest possible inversion (i, j) (smallest i, then smallest j > i with a[i] > a[j]) and swap them.
  Repeat until the array is sorted.

Example:
For the array [3, 2, 1]

• Swap indices (0,1) → [2, 3, 1]

• Swap indices (0,2) → [1, 3, 2]

• Swap indices (1,2) → [1, 2, 3]
  So the number of swaps required is 3.

The initial order can be any order, not necessary in decreasing order as above.

The straightforward solution is to directly simulate the process, which takes O(n²) in the worst case (since there can be O(n²) inversions).

My question:
Is there a more efficient algorithm (better than quadratic time) to compute the number of swaps, without having to explicitly simulate each step?

What I have tried / thought about:

• The problem is similar to inversion counting (which can be done in O(n log n)), but the lexicographical constraint changes the order of swaps compared to simply counting inversions.

• I considered adapting a Fenwick Tree (BIT) or Segment Tree to simulate the process more efficiently, but I haven’t yet figured out how to model the lexicographical requirement correctly.

Any ideas on how to approach this problem more efficiently, or references to similar problems, would be very helpful.

CODE implementation:

function lexicographical_swaps(arr):
    n = length(arr)
    swaps = 0

    while not is_sorted(arr):
        # Step 1: find earliest inversion
        for i in 0..n-2:
            found = false
            for j in i+1..n-1:
                if arr[i] > arr[j]:
                    # inversion found: earliest (i, j)
                    swap(arr[i], arr[j])
                    swaps += 1
                    found = true
                    break
            if found:
                break

    return swaps

Answer 1

Whenever a lexicographical swap is performed on indexes (i, j), it must be the case that a[j] is the closest smaller element to the right of a[i] and the subarray before index i is sorted (otherwise, this wouldn't be the lexicographically smallest inversion). Since a[j] is the closest smaller element, all elements between i and j are greater than or equal to a[i]. As such, after the swap, the new element at index j will still need to swap (directly or indirectly) with the elements between i and j that are not equal to its value. Whenever there are duplicate elements, the swap will always occur with the one with the lowest index, so it is only necessary to consider distinct elements in that range. The number of swaps caused by a particular array element is equal to the number of distinct preceding larger elements. With a balanced binary search tree, we can obtain these values in O(n log n).

Here is a C++ implementation (leveraging GCC's policy-based data structures):

#include <span>
#include <cstddef>
#include <ext/pb_ds/assoc_container.hpp>
#include <functional>
template<typename T, typename C=std::less<>>
using ordered_set = __gnu_pbds::tree<T, __gnu_pbds::null_type, C, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update>;

std::size_t lexicographicalSwaps(std::span<int> nums) {
    ordered_set<int, std::greater<>> prev;
    std::size_t swaps{};
    for (int num : nums) {
        swaps += prev.order_of_key(num);
        prev.insert(num);
    }
    return swaps;
}