Fenwick tree O(n log n) (80 ms)
To get this solution read about Fenwick tree\n\n### Complexity\n> - Time complexity:\nO(n log n)\n> - Space complexity:\nO(n)\n\n## Code\n\nuse std::collections
###### To get this solution read about [Fenwick tree](https://en.wikipedia.org/wiki/Fenwick_tree#:~:text=A%20Fenwick%20tree%20or%20binary,in%20an%20array%20of%20values.&text=This%20structure%20was%20proposed%20by,further%20modification%20published%20in%201992)\n\n### Complexity\n> - Time complexity:\n$$O(n$$ $$log n)$$\n> - Space complexity:\n$$O(n)$$\n\n## Code\n```\nuse std::collections::HashMap;\n\nstruct FT {\n    tree:  Vec<usize>,\n    treen: i32\n}\n\nimpl FT {\n    fn new(max: usize) -> FT {\n        FT {\n            tree:  vec![0; max + 2],\n            treen: (max + 2) as i32\n        }\n    }\n\n    fn update(&mut self, mut pos: i32, val: usize) {\n        while pos < self.treen {\n            self.tree[pos as usize] += val;\n            pos += pos & -pos;\n        }\n    }\n\n    fn sum(&self, mut pos: i32) -> usize {\n        let mut ans = 0;\n        while pos > 0 {\n            ans += self.tree[pos as usize];\n            pos -= pos & -pos;\n        } ans\n    }\n}\n\nmacro_rules! push {\n    ($arr: ident <- $i: expr, $n: ident++, $ft: ident <- $id: ident) => {\n        $arr.push($i); $n += 1;\n        $ft.update($id, 1);\n    };\n}\n\nimpl Solution {\n    pub fn result_array(nums: Vec<i32>) -> Vec<i32> {\n        let n = nums.len();\n\n        let (mut arr1, mut arr2) = (Vec::with_capacity(n), Vec::with_capacity(n));\n        let (mut n1,   mut n2  ) = (1, 1);\n        let (mut map,  mut mapn) = (HashMap::with_capacity(n), 0);\n\n        let mut sorted = nums.clone(); sorted.sort_unstable();\n        sorted.iter().for_each(|i| {\n            map.entry(i).or_insert(mapn + 1); mapn += 1;\n        });\n\n        let (mut ft1, mut ft2) = (FT::new(mapn as usize), FT::new(mapn as usize));\n        arr1.push(nums[0]);\n        ft1.update(*map.get(&nums[0]).unwrap(), 1);\n\n        arr2.push(nums[1]);\n        ft2.update(*map.get(&nums[1]).unwrap(), 1);\n        nums.iter().skip(2).for_each(|&i| {\n            let id  = *map.get(&i).unwrap();\n            let gc1 = n1 - ft1.sum(id);\n            let gc2 = n2 - ft2.sum(id);\n\n            if gc1 > gc2 {\n                push!(arr1 <- i, n1++, ft1 <- id);\n            } else if gc1 < gc2 {\n                push!(arr2 <- i, n2++, ft2 <- id);\n            } else {\n                if n2 < n1 {\n                    push!(arr2 <- i, n2++, ft2 <- id);\n                } else {\n                    push!(arr1 <- i, n1++, ft1 <- id);\n                }\n            }\n        });\n        arr1.append(&mut arr2);\n        arr1\n    }\n}\n```\n\n> By the way, this is not mine solution entirely; that\'s an improved(in my opinion) version of the fastest solution from the Leetcode submissions graph. I\'d reference the author of the initial solution, but unfortunately, i don\'t have that contact.\n\n![image.png](https://assets.leetcode.com/users/images/447f7b56-2855-467c-ae1b-f8b1a8e95c04_1709746270.9753578.png)\n
['Binary Indexed Tree', 'Rust']