Space Complexity of Various Sorting Algorithms

The input space for all sorting algorithms is at least O(n), where n is the size of the array. It is also important to understand the auxiliary space being used by that algorithm.

1. Bubble sort: The sorting is done in place and there is generally one extra variable used to store the temporary location for swapping successive items. Hence, the auxiliary space used is O(1).
2. Insertion sort: The case is the same as bubble sort. The sorting is done in place with a constant number of extra variables, so the auxiliary space used in O(1).
3. Merge sort: In merge sort, we split the array into two and merge the two sub-arrays by using a temporary array. The temporary array is the same size as the input array, hence, the auxiliary space required is O(n).
4. Heap sort: Heap sort is also implemented in place and hence the auxiliary space required is O(1).
5. Quick sort: Depending on how you implement quick sort, generally you would need O(log(n)) additional space to sort an array.