5 ms·

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/algo

by aidanhs 12y ago

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/listsort.html http://www.chiark.greenend.org.uk/~sgtatham/algorithms/lists... I think it's interesting how choice of data structure affects algorithm characteristics.

wfunction 12y ago
I don't think people have linked lists in mind when they talk about merge sort.
- angersock 12y ago
  I was under the impression that the sorting of linked lists is exactly what merge sort is good for.
  - wfunction 12y ago
    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
    - angersock 12y ago
      Right, that's not the primary application of merge sort--I meant 1. English is hard sometimes. :(
StefanKarpinski 12y ago
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.
- wfunction 12y ago
  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.
  - aidanhs 12y ago
    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...
    - deleted 12y ago
      [deleted]
    - wfunction 12y ago
      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.
      - aidanhs 12y ago
        > 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.

by aidanhs 12y ago

wfunction 12y ago

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

angersock 12y ago
I was under the impression that the sorting of linked lists is exactly what merge sort is good for.
- wfunction 12y ago
  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
  - angersock 12y ago
    Right, that's not the primary application of merge sort--I meant 1. English is hard sometimes. :(

StefanKarpinski 12y ago

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.

wfunction 12y ago
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.
- aidanhs 12y ago
  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...
  - deleted 12y ago
    [deleted]
  - wfunction 12y ago
    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.
    - aidanhs 12y ago
      > 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.