Binary Search + Insertion Sort
Intuition\n Describe your first thoughts on how to solve this problem. \nBinary Search & Insertion Sort\n\n# Approach\n Describe your approach to solving the pr
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nBinary Search & Insertion Sort\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\nBinary Search : the index of array which is larger than value\nInsertion Sort : add value to the right place to sorted array\n\n\n# Complexity\n- Time complexity: O(n^2)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(n)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    fun resultArray(nums: IntArray): IntArray {\n        val arr1 = mutableListOf(nums[0])\n        val arr2 = mutableListOf(nums[1])\n        val a1 = mutableListOf(nums[0])\n        val a2 = mutableListOf(nums[1])\n        \n        for (i in 2 until nums.size) {\n            val v = nums[i]\n            val x = greaterCount(arr1, v)\n            val y = greaterCount(arr2, v)\n            if (x > y || (x == y && arr1.size <= arr2.size)) {\n                arr1.add(arr1.size - x, v)\n                a1.add(v)\n            } else {\n                arr2.add(arr2.size - y, v)\n                a2.add(v)\n            } \n        }\n        \n        return (a1 + a2).toIntArray()\n    }\n    private fun greaterCount(arr: List<Int>, v: Int): Int {\n        var left = 0\n        var right = arr.size - 1\n        var result = arr.size\n        while (left <= right) {\n            var mid = left + (right - left) / 2\n            if (arr[mid] <= v) left = mid + 1\n            else {\n                result = mid\n                right = mid - 1\n            }\n        }\n        return arr.size - result\n    }\n}\n```
['Kotlin']