Re:Parallel In-Place Merge Sort
by wfunction on Wednesday October 01, 2014 @01:31PM
(#8396194)
Yeah, exactly. For those who didn't catch it: linked lists already have O(log n) overhead, because distinguishing between n items requires log n bits for the pointer. They're fundamentally not in-place.
[ Parent
| on HN ]
Hmm, I was thinking 'in-place' in the context of 'no extra memory needed'. Is this not correct?
For sure, if it doesn't make sense to use a linked list in the first place then linked list merge sort definitely doesn't make sense...
It's not that it's incorrect, it's that it's pointless. The entire point of a linked list is that you don't move around the data, you just re-link nodes. So any sane algorithm that works on linked lists is already "in-place" by default; an out-of-place merge on a linked list would be pure madness. So saying that an in-place merge can be performed on a data structure that already has some overhead and which already performs everything in place is not a very insightful or useful observation.
> an out-of-place merge on a linked list would be pure madness
Absolutely. I'm not even sure how you would do such a thing.
I personally have found it interesting when considering the difference between an array of pointers and a linked list, simply because they both have the same overhead but one doesn't require allocating any more memory for a merge sort.
I basically agree with what you say (maybe bar it not being useful knowledge) but I don't think it's worth continuing trying to clarify my initial statement.