Very simple C++/Python/Java O(n) soln (Avoid in-place swapping as the input is passed as reference)
C++\n\nvector<int> sortArrayByParity(vector<int>& A) {\n        int size = A.size();\n        vector<int> res(size, 0);\n        int start = 0, end = size - 1;\
***C++***\n```\nvector<int> sortArrayByParity(vector<int>& A) {\n        int size = A.size();\n        vector<int> res(size, 0);\n        int start = 0, end = size - 1;\n        for (int i = 0; i < size; i++) {\n            if (A[i] % 2 == 1) {\n                res[end--] = A[i];\n            } else {\n                res[start++] = A[i];\n            }\n        }\n        return res;\n    }\n```\n\n***Python***\n```\nclass Solution(object):\n    def sortArrayByParity(self, A):\n        """\n        :type A: List[int]\n        :rtype: List[int]\n        """\n        size = len(A)\n        res = [None] * size\n        start = 0\n        end = size - 1\n        for val in A:\n            if val % 2 == 1:\n                res[end] = val\n                end = end -1\n            else:\n                res[start] = val\n                start = start + 1\n        return res\n```\n\n***Java***\n\n```\nclass Solution {\n    public int[] sortArrayByParity(int[] A) {\n        int size = A.length;\n        int start = 0, end = size - 1;\n        int[] res = new int[size];\n        for (int i = 0; i < size; i++) {\n            if (A[i] % 2 == 1) {\n                res[end--] = A[i];\n            } else {\n                res[start++] = A[i];\n            }\n        }\n        return res;\n    }\n}\n```
[]