In each value of count, there are nested iterations. To create left and right, it need the O(n/count), and the merge one is O(count). So, the complexity is still like O(n/count) * O(count) = O(n) ?
I am not good at the algorithm. That's the reason I don't know how to calculate the complexity.
I was only able to solve the problem in O(2N) with Hashtable. With O(NLogN) I got TLE on large input.
Is O(n log(n)) because:
Splits the list again and again at half:
n + 2*n/2 + 4*n/4 + 8*n/8 ... until the result n/d is one.
This means that runs n * log2n.
Doesn't matter if in any recursion traverse one to get the middle and again to merge.
n + n is still n
This is the way works the complexity indicator.