template <typename RandomAccessIterator>

int countInversions (RandomAccessIterator first, RandomAccessIterator last);

Count the number of inversions in the range. The items in the range will not be changed.


first, last

Random access iterators to the initial and final positions of the sequence. The range used is [first,last), which contains all the elements between first and last, including the element pointed by first but not the element pointed by last.

Return value

Number of inversions in the range.


#include <iostream>
#include "HKUAL_order.h"

using namespace std;
using namespace HKUAL;
int main(){
    int mylist[] ={1, 3, 5, 4, 2, 0};
    cout << "Number of inversions = " << countInversions(mylist, mylist + 6) << endl;
    return 0;


Number of inversions = 9

Time Complexity

, n is the number of items in the range.

© The University of Hong Kong Algorithms Library -