4 ms·
The term "in-place" almost always means O(1) additional space, whereas this uses O(n) additional space.
by cwzwarich 7y ago
The term "in-place" almost always means O(1) additional space, whereas this uses O(n) additional space.
- deleted 7y ago[deleted]
- gpderetta 7y agotechnically quick sort needs O(log N) additional space and it is still considered in-place. I guess the threshold for in-place-ness would be less than linear additional space?
- utopcell 7y agoquicksort is not stable. the disadvantage of classic mergesort is that it needs to copy elements out of the input array, although there exist (slower) in-place variations.