O(n*sqrt(n)) Solution || C++
Approach\nI keep track of two vectors for each arrays, one sorted and one is unsorted. When adding elements to one of the arrays, I add them to the unsorted arr
# Approach\nI keep track of two vectors for each arrays, one sorted and one is unsorted. When adding elements to one of the arrays, I add them to the unsorted array until its size reaches $$\\sqrt{n}$$. Then I sort the unsorted array and merge it with the sorted array. I also empty the unsorted array. When counting the greaterCount for one of the arrays, I binary search the sorted array and brute force the unsorted array. Calculating the greaterCount costs $$O(\\sqrt{n} + \\log{n})$$, so $$O(\\sqrt{n})$$. Merging the unsorted array with the sorted array costs $$\\sqrt{n}*\\log{\\sqrt{n}} + O(n)$$. The arrays are merged at most $$\\sqrt{n}$$ times, since there are n elements and I only merge if the unsorted array size reaches length $$\\sqrt{n}$$ . The total merging cost is $$O(n\\sqrt{n})$$\n# Complexity\n- Time complexity: $$O(n\\sqrt{n})$$\n\n- Space complexity: $$O(n)$$\n\n# Code\n```\nclass Solution {\npublic:\n    \n    void merge(vector<int>& v1, vector<int>& v2){\n        vector<int> res;\n        sort(v2.begin(), v2.end());\n        int idx1 = 0, idx2 = 0;\n        while(idx1 != v1.size() || idx2 != v2.size()){\n            if(idx1 == v1.size()){\n                res.push_back(v2[idx2]);\n                idx2++;\n            }\n            else if(idx2 == v2.size()){\n                res.push_back(v1[idx1]);\n                idx1++;\n            }\n            else if(v1[idx1] < v2[idx2]){\n                res.push_back(v1[idx1]);\n                idx1++;\n            }\n            else{\n                res.push_back(v2[idx2]);\n                idx2++;\n            }\n        }\n        \n        v1 = res;\n        v2.clear();\n    }\n    \n    vector<int> resultArray(vector<int>& nums) {\n        vector<int> v1, v2;\n        vector<int> extrav1, extrav2;\n        vector<int> ans1, ans2;\n        \n        int root = sqrt(nums.size());\n        \n        v1.push_back(nums[0]);\n        v2.push_back(nums[1]);\n        ans1.push_back(nums[0]);\n        ans2.push_back(nums[1]);\n        \n        for(int i = 2; i < nums.size(); i++){\n            int cnt1 = v1.size() - (upper_bound(v1.begin(), v1.end(), nums[i]) - v1.begin());\n            int cnt2 = v2.size() - (upper_bound(v2.begin(), v2.end(), nums[i]) - v2.begin());\n            for(auto& k : extrav1){\n                if(k > nums[i]) cnt1++;\n            }\n            \n            for(auto& k : extrav2){\n                if(k > nums[i]) cnt2++;\n            }\n            \n            if(cnt1 > cnt2 || (cnt1 == cnt2 && v1.size() + extrav1.size() <= v2.size() + extrav2.size())){\n                extrav1.push_back(nums[i]);\n                ans1.push_back(nums[i]);\n                if(extrav1.size() == root){\n                    merge(v1, extrav1);\n                }\n            }\n            else{\n                extrav2.push_back(nums[i]);\n                ans2.push_back(nums[i]);\n                if(extrav2.size() == root){\n                    merge(v2, extrav2);\n                }\n            }\n        }\n        for(auto& k : ans2){\n            ans1.push_back(k);\n        }\n        return ans1;\n    }\n};\n```
['C++']