Ok, good, but why this works?

There is only 6 large test

Your code might not actually be O(n log n). If you only manage the first 5 large tests, I really doubt it is.

Post your code, maybe we can say something. If your code really is O(n log n), it would have to be horribly inefficient to fail so soon, and you would probably be able to optimise it yourself ( maybe not enough, but usefully, at least ).

I'd look up test driven development. Two different data structures can perform the given operation, one may take a lot longer though given the task and requirements to fulfill your test. One data structure can provide the operation instantaneously, while the other has to go through the process which may take longer. Such an example is a hash table in python(I would google this if you haven't learned this already). The mathematics portion you asked for a hint about seems to be to be an advanced understanding of math, but the exact keyword to help you look up and understand, that I do not know. This is what I can tell you with my current knowledge, it may not be the whole picture and entirely accurate, but the idea should be similiar.

Let's say i have an algorithm that gives me the right array with time complexity of O(nlog(n)), more precise nlog(n)+2n. Maybe i can just optimize some instruction here and there, change the while statement with for...but i only pass the first 5 large test. Is there any hint about mathematical properties that i should care about? because i cannot think an algorithm more optimized than that, there must be some tricks, maybe with the structure/composition of the original array...pls help!

Unbelievable

It is.

it will never happen, because the second bigger vector is also of type int

Hey, did you find out what the weird bit of code does? Anyone?

i1 instead of j --> BLEAH

HOW???

What? HOW?????

What???