Inversion Count
(algo/sequence/inversion_count.hpp)

• View this file on GitHub
• Last update: 2026-07-07 21:49:48+09:00
• Include: #include "algo/sequence/inversion_count.hpp"

Overview

Calculates the number of inversions in a sequence. An inversion is a pair of indices (i, j) such that i < j and a[i] > a[j].

The implementation uses merge sort and does not require coordinate compression.

The return type is long long because a sequence of size $N$ can have $N(N-1)/2$ inversions.

Template Parameters

• T: Element type. Values must be comparable using <.

Methods

Method	Description	Complexity
long long inversion_count(std::vector<T> a)	Returns the total number of inversions. The argument is taken by value. Use std::move(a) if you no longer need the original array to avoid an $O(N)$ copy.	$O(N \log N)$ time, $O(N)$ space

Example

#include "algo/sequence/inversion_count.hpp"
#include <iostream>
#include <vector>

int main() {
    std::vector<int> a = {2, 4, 1, 3, 5};

    const long long inversions = m1une::algo::inversion_count(a);

    // The inversions are:
    // (2, 1) -> indices 0 and 2
    // (4, 1) -> indices 1 and 2
    // (4, 3) -> indices 1 and 3
    std::cout << "Inversions: " << inversions << "\n"; // Output: 3

    // To avoid copying the array if you don't need it afterward:
    // long long fast_invs = m1une::algo::inversion_count(std::move(a));

    return 0;
}

Required by

• Algorithms All (algo/all.hpp)
• Sequence Algorithms All (algo/sequence/all.hpp)

Verified with

• verify/algo/sequence/sequence_algorithms.test.cpp

Code

#ifndef M1UNE_ALGO_SEQUENCE_INVERSION_COUNT_HPP
#define M1UNE_ALGO_SEQUENCE_INVERSION_COUNT_HPP 1

#include <vector>

namespace m1une {
namespace algo {

// Returns the number of pairs (i, j) with i < j and a[i] > a[j].
// The vector is taken by value because merge sort rearranges it.
template <typename T>
long long inversion_count(std::vector<T> a) {
    const int n = int(a.size());
    std::vector<T> temp = a;

    auto merge_sort = [&](auto& self, int l, int r) -> long long {
        if (r - l <= 1) return 0;

        const int m = l + (r - l) / 2;
        long long inv = self(self, l, m) + self(self, m, r);

        int i = l;
        int j = m;
        int k = l;
        while (i < m && j < r) {
            if (!(a[j] < a[i])) {
                temp[k++] = a[i++];
            } else {
                temp[k++] = a[j++];
                inv += m - i;
            }
        }

        while (i < m) temp[k++] = a[i++];
        while (j < r) temp[k++] = a[j++];

        for (int p = l; p < r; ++p) {
            a[p] = temp[p];
        }

        return inv;
    };

    return merge_sort(merge_sort, 0, n);
}

}  // namespace algo
}  // namespace m1une

#endif  // M1UNE_ALGO_SEQUENCE_INVERSION_COUNT_HPP

#line 1 "algo/sequence/inversion_count.hpp"



#include <vector>

namespace m1une {
namespace algo {

// Returns the number of pairs (i, j) with i < j and a[i] > a[j].
// The vector is taken by value because merge sort rearranges it.
template <typename T>
long long inversion_count(std::vector<T> a) {
    const int n = int(a.size());
    std::vector<T> temp = a;

    auto merge_sort = [&](auto& self, int l, int r) -> long long {
        if (r - l <= 1) return 0;

        const int m = l + (r - l) / 2;
        long long inv = self(self, l, m) + self(self, m, r);

        int i = l;
        int j = m;
        int k = l;
        while (i < m && j < r) {
            if (!(a[j] < a[i])) {
                temp[k++] = a[i++];
            } else {
                temp[k++] = a[j++];
                inv += m - i;
            }
        }

        while (i < m) temp[k++] = a[i++];
        while (j < r) temp[k++] = a[j++];

        for (int p = l; p < r; ++p) {
            a[p] = temp[p];
        }

        return inv;
    };

    return merge_sort(merge_sort, 0, n);
}

}  // namespace algo
}  // namespace m1une

Back to top page