Aufgabe «Mergesort mit Inversionszählung»

Gegeben ist ein Array von ganzen Zahlen. Es muss mit Hilfe von Mergesort aufsteigend sortiert werden, und zusätzlich die Anzahl der Inversionen im ursprünglichen Array gezählt werden. Eine Inversion ist ein Indexpaar (i, j), für das i < j und a[i] > a[j] gilt. Eingabedaten: Die erste Zeile enthält die Zahl n (1 ≤ n ≤ 10^5), die zweite Zeile enthält n ganze Zahlen, deren Betrag jeweils 10^9 nicht überschreitet. Ausgabedaten: Die erste Zeile ist die Anzahl der Inversionen, die zweite Zeile ist das sortierte Array, durch Leerzeichen getrennt.

Beispiel 1

Beispiel 2

Beispiel 3

Beispiel 4