How can a sorting algorithm have a space complexity of O(1)?

Question

I'm learning about different sorting algorithms and their time/space complexities and saw that algorithms such as bubble sort and insertion sort have a space complexity of O(1).

This struck me as weird, because surely the lowest space complexity possible would be O(n) (as in, the memory required to store the data set and nothing more)?

Solution 1

The space complexity is actually the additional space complexity used by your algorithm, i.e. the extra space that you need, apart from the initial space occupied by the data. Bubble-sort and insertion sort use only a constant additional space, apart from the original data, so they are O(1) in space complexity.

Solution 2

A sorting algorithm has space complexity O(1) by allocating a constant amount of space, such as a few variables for iteration and such, that are not proportional to the size of the input.

An example of sorting algorithm that is not O(1) in terms of space would be most implementations of mergesort, which allocate an auxiliary array, making it O(n). Quicksort might look like O(1) in theory, but the call stack counts like space and therefore it is said to be O(log n).

Examples of sorting algorithms with O(1) space complexity include: selection sort, insertion sort, shell sort and heapsort.

Solution 3

Bottom-up merge sort can be written in a such a way that it uses only constant extra space. This is an example of an asymptotically optimal sort (O(n*log(n))) while only using O(1) space.

Edit: This answer was kind of careless. Bottom up merge sort only uses O(1) space on a linked list. For a sort that uses O(1) space on an array, heapsort is your best bet. This is done by turning the array into a max heap in place, and then delete-max is called repeatedly with the value being stores at the back of the array. When the heap is empty, the array is sorted.

Comments

[Codor]

Not to forget bubblesort.

[arboreal84]

Bubble sort has quadratic time complexity and other than in academic settings it is never used.

[Codor]

You are right, but this was not my point. It has a constant space complexity, a polynomial running time and is the first algorithm one would naively come up with.

[Ray Toal]

Good to bring it up as a well-known algorithm that many readers of this site will have heard about, but as far as it being the first algorithm one would naively come up with, I'm not so sure. Maybe some people might. That would be an interesting study, come to think of it.... :)

[arboreal84]

I find selection sort and insertion sort better at introducing the concept of sorting. But it is a matter of preference.

[templatetypedef]

While this is true, it doesn’t directly answer the question posted here. Perhaps this should be a comment?

[Asad-ullah Khan]

I think you're right actually, might've jumped the gun on this one. I was just surprised no one had mentioned one of the few optimal O(1) sorts