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.
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.)
Comments
I’ll read the article when I get the chance, but would this be in-place?
From the article:
"These operations do require doubling the memory overhead for the swap space."
It seems it is not in-place.
Swap space is allocated here: https://github.com/scandum/quadsort/blob/c3bcf139c59eb296b28...
Okay, that looks like it is proportional to the size of the array, so definitely 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.
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.)
It looks like it is doubling the "swap space" used in a standard merge sort, not the "swap space" use in a quicksort.
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;
No. He uses a temporary array for swaps. It's in the swap example he provided.