Let A be an array of N distinct positive numbers such that at most sqrt(N) of them is larger than N.

Ex: if N=100, there are at most 10 elements in A that are greater than 100.

1. Split A into A1 and A2 such that A1 contains the elements greater than N and A2 contains the remaining elements. Do this in O(N)

2. Sort A1 in O(N)

3. Sort A2 in O(N)

4. Sort A in O(N)

I don't need actual code, more so it explained clearly. I was under the impression 3 and 4 would be impossible. Thanks!