Hacker News Reader

Comment by aidanhs | Hacker News Reader

A stable in-place merge sort is actually reasonably easy to implement if you happen to be using a linked list - http://www.chiark.greenend.org.uk/~sgtatham/algorithms/lists...

I think it's interesting how choice of data structure affects algorithm characteristics.

View on HN

Using a linked list is effectively equivalent to doing things not in place. Except that the memory locality is worse and for word-sized data like integers and floats, the overhead is permanent 3x instead of just temporary 2x. But yes, for linked lists, merge sort is a great choice since it doesn't depend on O(1) indexing.

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.

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.

I don't think people have linked lists in mind when they talk about merge sort.

I was under the impression that the sorting of linked lists is exactly what merge sort is good for.

You're confusing two things:

1. Yes, merge sort is exactly the kind of algorithm you'd use for sorting linked lists

2. No, sorting linked lists is not the primary application of merge sort

Right, that's not the primary application of merge sort--I meant 1. English is hard sometimes. :(

Reply on news.ycombinator.com