A linked list node is two words: a content word, and a next pointer. The contents are all you really care about; the next pointer is pure overhead: an implementation detail. So there’s a sense in which this doesn’t avoid the linear-space overhead of the mergesort; you were just forced to pay it anyway. (I find the issue of in-place algorithms a bit weird anyway—it makes sense to me to be concerned about an algorithm that uses superlinear space, but linear or sublinear space overhead just corresponds to bloating each element by a constant factor.)
A more practical issue: a naive list sort is obligatorily going to be about half pointer-chasing by volume, which is not so nice. And precludes important techniques like vectorisation and distribution. If I needed a fast sorting algorithm for lists, I would probably do something like the following:
Allocate a buffer of 2n words, and unload just the contents into the first half. Do a dense sort on the contents (could be out-of-place—use the latter half of the buffer if desired—or not; either way). Once done, explode the elements, so they fill the even indices of the buffer (in practice, this would be fused with the base case of the sorting algorithm), and fill every odd index with a pointer to the next even index (except for the last index, which is filled with a null pointer). Now a pointer to the base of the buffer is a pointer to the first node in the desired sorted list; and, further, the list nodes are contiguous and ordered in memory, so traversal will be fast (whereas an in-place sort as proposed in tla would probably have completely scrambled the order of a list which started out linear, assuming a good gc).
A more practical issue: a naive list sort is obligatorily going to be about half pointer-chasing by volume, which is not so nice. And precludes important techniques like vectorisation and distribution. If I needed a fast sorting algorithm for lists, I would probably do something like the following
That’s a pretty specific definition of “nice” you have. I like C to be nice C; in my view almost nothing that uses CPU resources optimally is nice, because it’s usually more complicated than I like. More of a necessary evil.
Anyway, I think most good uses of linked lists are intrusive (so moving nodes isn’t acceptable) and not traversed often. With that in mind I guess I’d sort an array of pointers to nodes and then overwrite all the next pointers from it. Or, if your values happen to be words you can just copy, why are you using a list? but then sort an array of (word, pointer), which I’d hope is a bit faster, and then overwrite the pointers from the array, ignoring the sorted values. But obviously both our solutions still have to traverse the list, so there’s still pointer chasing, just a bit less.
Of course in practice I’d just use merge sort because if you’re doing this often enough to care about the unnecessary pointer chasing you’re probably using the wrong datastructure.
Oh, btw, this link is ancient. It appears in the Internet Archive in 2001. I have suggested accordingly.
Implementing in-place merge sort for linked lists was the last question in my DSA final exam. I ran out of time and found this page after the fact. I’m still a little mad about it
A linked list node is two words: a content word, and a next pointer. The contents are all you really care about; the next pointer is pure overhead: an implementation detail. So there’s a sense in which this doesn’t avoid the linear-space overhead of the mergesort; you were just forced to pay it anyway. (I find the issue of in-place algorithms a bit weird anyway—it makes sense to me to be concerned about an algorithm that uses superlinear space, but linear or sublinear space overhead just corresponds to bloating each element by a constant factor.)
A more practical issue: a naive list sort is obligatorily going to be about half pointer-chasing by volume, which is not so nice. And precludes important techniques like vectorisation and distribution. If I needed a fast sorting algorithm for lists, I would probably do something like the following:
Allocate a buffer of 2n words, and unload just the contents into the first half. Do a dense sort on the contents (could be out-of-place—use the latter half of the buffer if desired—or not; either way). Once done, explode the elements, so they fill the even indices of the buffer (in practice, this would be fused with the base case of the sorting algorithm), and fill every odd index with a pointer to the next even index (except for the last index, which is filled with a null pointer). Now a pointer to the base of the buffer is a pointer to the first node in the desired sorted list; and, further, the list nodes are contiguous and ordered in memory, so traversal will be fast (whereas an in-place sort as proposed in tla would probably have completely scrambled the order of a list which started out linear, assuming a good gc).
That’s a pretty specific definition of “nice” you have. I like C to be nice C; in my view almost nothing that uses CPU resources optimally is nice, because it’s usually more complicated than I like. More of a necessary evil.
Anyway, I think most good uses of linked lists are intrusive (so moving nodes isn’t acceptable) and not traversed often. With that in mind I guess I’d sort an array of pointers to nodes and then overwrite all the next pointers from it. Or, if your values happen to be words you can just copy, why are you using a list? but then sort an array of (word, pointer), which I’d hope is a bit faster, and then overwrite the pointers from the array, ignoring the sorted values. But obviously both our solutions still have to traverse the list, so there’s still pointer chasing, just a bit less.
Of course in practice I’d just use merge sort because if you’re doing this often enough to care about the unnecessary pointer chasing you’re probably using the wrong datastructure.
Oh, btw, this link is ancient. It appears in the Internet Archive in 2001. I have suggested accordingly.
Implementing in-place merge sort for linked lists was the last question in my DSA final exam. I ran out of time and found this page after the fact. I’m still a little mad about it