Java merge sort O(nlogn)
Idea: from problem 315, find how many numbers smaller than self afterwards.\n\nclass Solution {\n    class Item {\n        int value;\n        int index;\n     
Idea: from problem 315, find how many numbers smaller than self afterwards.\n```\nclass Solution {\n    class Item {\n        int value;\n        int index;\n        int cnt = 0;\n        public Item(int value, int index) {\n            this.value = value;\n            this.index = index;\n        }\n        \n        public String toString() {\n            return String.format("{%s, %s, %s}", value, index, cnt);\n        }\n    }\n    \n    public boolean isTransformable(String s, String t) {\n        char[] arr = s.toCharArray(), tar = t.toCharArray();\n        if(arr.length != tar.length || !sameComp(arr, tar)) return false;\n        \n        int n = s.length();\n        Item[] items1 = getRevPair(arr), items2 = getRevPair(tar);\n        for(int i = 0; i < n; i++) {\n            if(items1[i].cnt < items2[i].cnt) return false;\n        }\n        return true;\n    }\n    \n    private Item[] getRevPair(char[] arr) {\n        int n = arr.length;\n        Item[] items = new Item[n];\n        for(int i = 0; i < n; i++) items[i] = new Item(arr[i] - \'0\', i);\n        mergeSort(items, 0, n-1);\n        return items;\n    }\n    \n    private void mergeSort(Item[] items, int start, int end) {\n        if(start == end) return;\n        int mid = (start + end) / 2;\n        mergeSort(items, start, mid);\n        mergeSort(items, mid+1, end);\n        merge(items, start, mid, mid+1, end);\n    }\n    \n    private void merge(Item[] items, int s1, int e1, int s2, int e2) {\n        int p = s1, q = s2;\n        List<Item> list = new ArrayList<>();\n        int cnt = 0;\n        while(p <= e1 && q <= e2) {\n            if(items[p].value <= items[q].value) {\n                items[p].cnt += cnt;\n                list.add(items[p]);\n                p++;\n            }\n            else {\n                list.add(items[q++]);\n                cnt++;\n            }\n        }\n        while(p <= e1) {\n            items[p].cnt += cnt;\n            list.add(items[p]);\n            p++;\n        }\n        while(q <= e2) list.add(items[q++]);\n        for(int i = 0; i < list.size(); i++) items[s1+i] = list.get(i);\n    }\n    \n    private boolean sameComp(char[] a, char[] b) {\n        int[] ac = new int[10], bc = new int[10];\n        for(char c: a) ac[c-\'0\']++;\n        for(char c: b) bc[c-\'0\']++;\n        for(int i = 0; i < 10; i++) {\n            if(ac[i] != bc[i]) return false;\n        }\n        return true;\n    }\n}\n```
[]