Inversions in an Array

Internal

• Algorithms | Divide and Conquer

Problem

Given an array containing n numbers, in an arbitrary order, find all inversions, where an inversion is defined as a pair (i, j) of array elements where i < j and A[i] > A[j]. Note that i and j need not be adjacent (in this case the inversion is called "out of order").

TODO

• problem statement
• algorithm
• complexity with Master Method

Overview

[Next]