Let's consider insertion sort.
void insertionSortRecursive(int arr[], int n)
{
// Base case
if (n <= 1)
return;
// Sort first n-1 elements
insertionSortRecursive( arr, n-1 );
// Insert last element at its correct position
// in sorted array.
int last = arr[n-1];
int j = n-2;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > last)
{
arr[j+1] = arr[j];
j--;
}
arr[j+1] = last;
}
Stack space is just the number of stack records required which is the number of function calls done, whose worst case would be when we have greatest extent of recursive calls without backtracking.
If you see the recursive call in this. It says insertionSortRecursive( arr, n-1 ) which means it reduces the size of the array by 1 in each recursive call. Hence the recurrence relation for stack space becomes
T(n) = T(n-1) +1
which results in O(n)
Here quick sort being an inplace algorithm taking O(logn) stack space would require the least amount of space among all of them.
