Comparison-based sorts have O(1) complexity on the size of the elements being sorted. I.e., comparison between two numbers is a single instruction assuming numbers fit within a word. Even if you assume very very large numbers then comparison would be O(k), where k is number of bits needed to represent a number. So a more accurate runtime of O(nlogn) algorithms should be O(k.nlogn).

The runtime of this algorithm is O(n.2^k).