The fiddly detail here is that big-O notation can be used to measure the usage of any resource, not just time. The poster above noted that an in-place sort might have constant space complexity -- although this only makes sense if you discount the space required for the input anyhow (which is literally linear in the input size!).
Wikipedia distinguishes two measures of space, "total" (including the input) and "auxiliary" (excluding the input). The poster above you is likely referring to auxiliary space.
Sorry, wasn't clear. Was talking about the space complexity. If you sort in-place you don't need O(n) space, you can do with O(1 ). Not talking about time complexity
They mean the amount of storage, and they're only counting additional memory allocated by the algorithm, and not the memory containing the input.
Well... sorting a shuffled deck of cards can be done in O(1) time.
def sort(self):
pass
def __getitem__(i):
suit = int(i / 13)
rank = i % 13
return f"{rank} of {('diamonds', 'hearts', 'spades', 'clubs')[suit]}"
I'm certainly not a good theoretical computer scientist, but I did quickly google this and I couldn't find any trace of constant-time sorting (unless you goalpost it to have O(n log n) processors, but that is kind of cheating, here).