Gegeven een rij positieve gehele getallen \((a_0,\ldots,a_{n-1})\). Je mag veronderstellen dat alle getallen verschillend zijn. Een inversie is een paar \(i<j\) waarvoor \(a_i>a_j\).

Ontwerp en implementeer een \(\Theta(n \, \log n)\) algoritme dat het aantal inversies in een gegeven rij telt.

Opgave

Schrijf een Python-functie telInversies(rij: list) die het aantal inversies in de gegeven rij bepaalt en teruggeeft.

Voorbeelden

>>> telInversies([2, 4, 3, 1, 5])
4
>>> telInversies([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
0
>>> telInversies([10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0])
55