問題タブ [inversion]

整数の配列で反転をカウントするプロジェクトを作成するための学校からの宿題があります。最初は総当たりでやってみましたが、さすがに制限時間は過ぎませんでした。したがって、いくつかのグーグル検索とmergeSortとそれに反転のカウントを実装する方法を完全に理解しようとした後、配列を正しくソートしながら、残念ながら間違ったカウントを出力するこのコードを作成しました:

ご協力いただきありがとうございます。宣言の愚かな間違いであることは知っていますが、それを見つけることができないようです。

私は、順列番号のソートされていないリストの反転の数をカウントするために、以下の疑似コードに従うコードを考え出すのに数日間苦労してきました。O(nlogn) 時間で実行するアルゴリズムが必要ですが、O(n^2logn) 時間でしか解決策を思いつきません。

より具体的には、ネストされた for ループを使用せずに 2 番目のステップを高速化する方法を知りたいです。動作する他の効率的なアルゴリズム (つまり、マージソート) があることは知っていますが、疑似コードの手順に従う必要があります。

これまでに思いついたコードは次のとおりです。

注: アルゴリズムは、リスト内の反転の数をスカラーで返す必要があります。疑似コードは配列を要求しますが、最終的に配列の要素を合計して反転カウントを計算します。