I’m kind of confused between these two terms as for example – the Auxiliary space of merge sort, heapsort and insertion sort is O(1) whereas Space complexity of merge sort, insertion sort, heapsort is O(n).
So, if someone asks me what’s the Space complexity of merge sort, heapsort or insertion sort then what should I tell them O(1) or O(n)?
Also, note in case of selection sort, I’ve read it’s Space Complexity is O(1) which is auxiliary space.
In Algorithms fourth edition by Robert Sedgewick and Kevin Wayne, the exercise 2.2.10 states that:
Implement a version of merge() that copies the second half of a to aux in decreasing order and then does the merge back to a. This change al- lows you to remove the code to test that each of the halves has been exhausted from the inner loop.
This is my code in Python:
def merge(a, lo, mi, hi): aux_hi = deque(a[mi:hi]) for i in range(lo, hi)[::-1]： if aux_hi: last_a = i-len(aux_hi) if last_a < lo: a[i] = aux_hi.pop() else: a[i] = aux_hi.pop() if aux_hi[-1] > a[last_a] else a[last_a] else: break
Have I implemented it as required? Or can it be improved further?