Hacker News new | past | comments | ask | show | jobs | submit login

From the article:

"These operations do require doubling the memory overhead for the swap space."

It seems it is not in-place.






I'm pretty sure it's in-place, thus the need for "swap space" to hold the values that are being moved.

The term "in-place" almost always means O(1) additional space, whereas this uses O(n) additional space.

technically 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?

quicksort 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.

It looks like it is doubling the "swap space" used in a standard merge sort, not the "swap space" use in a quicksort.

In place kinda means the opposite of in swap space.

But "swap space" without the "in" is pretty ambiguous. If it just holds 1 or 4 elements as you perform a single logical swap, you're still sorting in-place.

(This sort does not use the term that way, but another sort could.)


You technically do not need any swap space to swap two numbers. So algorithms which only use swaps could be implemented fully in place.

while you can indeed swap in-place for PODs [1], this is not true for c++ objects. Also, in-place swapping is not sufficient for in-place sorting.

[1] example: int a, b; a ^= b ^= a ^= b;



Okay, that looks like it is proportional to the size of the array, so definitely not in-place.



Applications are open for YC Summer 2020

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: