You are viewing a single comment's thread. Return to all comments →
Not all O(n log n) solutions will pass. Here is one example that fails (locality of reference does matter):
long countInversions(vector<int> arr) { long inversions = 0; const int bits = 24; vector<unordered_map<int, long>> counts(bits); for (auto iter = arr.crbegin(); iter < arr.crend(); iter++) { int item = *iter; // Read counts. { // scope int copy = item; for (int shifted = 0; shifted < bits; ++shifted) { if ((copy & 1) > 0) inversions += counts[shifted][copy - 1]; copy >>= 1; } } // Add to counts. { // scope int copy = item; for (int shifted = 0; shifted < bits; ++shifted) { counts[shifted][copy]++; copy >>= 1; } } } return inversions; }
Seems like cookies are disabled on this browser, please enable them to open this website
Merge Sort: Counting Inversions
You are viewing a single comment's thread. Return to all comments →
Not all O(n log n) solutions will pass. Here is one example that fails (locality of reference does matter):