Can someone help me understand the time and space complexity?
Assuming that sorted() really takes time $O(n)$, then the time and space complexities are indeed $O(n)$. Hoewever there are some catches.
You say that the zip function takes $O(1)$ time. This is technically true, but you should be aware that zip is not creating a list that contains pairs of elements from a and b but just returning an iterator to these pairs. Going through the list implicitly returned by this iterator takes $O(n)$ time, even just to construct it (e.g., list(zip(a,b))). In your particular case this doesn't really matter since the time complexity will be $\Omega(n)$ anyway.
You say that sorted() takes $O(n)$ time. This is not impossible, but it's at least suspicious (have you checked in the python documentation/implementation?). There is no algorithm that can sort a list of $n$ elements in time $O(n)$ by only performing comparisons. The implementation of sorted() would need to be particularly clever and recognize that you are sorting small integers.
Probably sorted() just takes $O(n \log n)$ time and $O(n)$ space, which would result in the same overall time and space complexities for your algorithm.