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 migh

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.