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