🔒 Merge Sort & Quick Sort Maximum Stack Depth

[sinful bronze]

Hi there, I have just started to learn about space complexity and I am wondering what the formula for the maximum stack depth of a merge sort and quick sort would be. The answers that I have come to are logn for merge sort and constant for quick sort but not sure.

[obtuse cipher]

@sinful bronze

Python help channel opened

Remember to:

• Ask your Python question, not if you can ask or if there's an expert who can help.
• Show a code sample as text (rather than a screenshot) and the error message, if you've got one.
• Explain what you expect to happen and what actually happens.

:warning: Do not pip install anything that isn't related to your question, especially if asked to over DMs.

Closes after a period of inactivity, or when you send !close.

[vague yarrow]

the space complexity of a sorting algorithm can only be O(1) if it's in-place

[sinful bronze]

Hmm okie so quick sort is an in-place sort so am I correct?

[vague yarrow]

no

[sinful bronze]

My prof said that quick sort is inplace

[vague yarrow]

huh. maybe I don't know stuff

officially, I got an A in graduate level algorithms

[lavish crypt]

maybe you meant not stable instead of not in-place

[vague yarrow]

no, I know what stability is for sure

[lavish crypt]

hm ok
in any case quicksort can be in place, if you implement it correctly

[vague yarrow]

(that is, a sorting algorithm is stable when, for two elements in the array that are considered equal for sorting purposes, their original order relative to each other is preserved in the final result)

[lavish crypt]

example:
say you had to sort these

(1, 'a'), (5, 'e'), (1, 'X'), (3, 'b'), (5, 'E')
```and the way you sort them is by considering the first number only
a stable sort would guarantee that `(1, 'a')` comes before `(1, 'X')`, and `(5, 'e')` came before `(5, 'E')`, because their order is the same, and one came before the other in the original

[obtuse cipher]

Python help channel closed

This help channel has been closed and it's no longer possible to send messages here. If your question wasn't answered, feel free to create a new post in #1035199133436354600. To maximize your chances of getting a response, check out this guide on asking good questions.