How can I sort a LinkedList with just the standard library?

Question

Vec provides a sort method (through Deref implementation), but LinkedList does not. Is there a generic algorithm somewhere in the Rust standard library that allows sorting of LinkedLists?

I doubt so, is destroying the list, allocating another container, and re-creating another list a viable solution? Because sorting linked lists does not work well. — Matthieu M., Jun 02 '15 at 15:19
Why do you say sorting linked lists does not work well? Merge sort is a nice way to sort a linked list... — wspeirs, Jun 02 '15 at 18:55
@wspeirs 'Cause linked lists are slow. It will almost surely be faster to go `LinkedList → Vec → LinkedList` than to sort in-place. Why do you have a `LinkedList` anyway? — Veedrac, Jun 02 '15 at 19:10
@Veedrac I'll admit this is more of an academic question than a practical one. Just curious if I was missing something from the standard library to sort a LinkedList. Both C++ and Java have such methods, curious why Rust does not, or if it does then how... — wspeirs, Jun 02 '15 at 19:23
@wspeirs Rust doesn't have such a method because nobody wants it. A `sort` for `RandomAccessIterator` might make sense, though, if people had reason for it. — Veedrac, Jun 02 '15 at 19:27
@wspeirs: The problem with theory and practice is that they are only identical in theory. In this case, while you can indeed get O(N log N) complexity with a linked-list, in practice it's generally slow because of cache misses and constant factors. C++ provides a `list.sort()` because `std::sort` requires random-access iterators thus a specialized version was required; but then C++ also provides `list.size()` which prevented O(1) splicing, so I am not sure it's a good idea. — Matthieu M., Jun 03 '15 at 06:17
@Veedrac We have yet to find a way to make a `RandomAccessIterator`-like abstraction work to allow sorting. The current RAI give read-only access. — bluss, Jun 03 '15 at 14:52

score 7 · Accepted Answer · edited May 23 '17 at 10:33

7

I don't think there is a built-in way to do it. However, you can move the list contents into a Vec, sort it and turn it back into a linked list:

let mut vec: Vec<_> = list.into_iter().collect();
vec.sort();
let list: LinkedList<_> = vec.into_iter().collect();

This idea is not even remotely as bad as it may seem - see here. While relatively fast algorithms for sorting a linked list do exist, they won't give you as much of cache performance as flat array sorting may do.

edited May 23 '17 at 10:33

Community

1
1

answered Jun 02 '15 at 15:21

Vladimir Matveev

120,085
34
287
296

The only thing I am worried about here is that consuming then re-allocating the list implies free-ing/re-allocating memory. I am wondering if the work in the vector could be *proxied*, ie, instead of transferring the list elements, you put references in the vector, and then sorting the vector actually mutates the list elements in place... or at the very least, instead of consuming the list you replace its elements by "dummies" and then replace the dummies again by the sorted values. – Matthieu M. Jun 02 '15 at 15:58
Yes, you're right about reallocating. I think something like `read_into_vec(list: &mut LinkedList, vec: &mut Vec)` unsafe function and its counterpart `read_into_list(vec: &mut Vec, list: &mut LinkedList)` (also unsafe), which move elements around without freeing them, could work, but one should be very careful around panics and destructors here. – Vladimir Matveev Jun 02 '15 at 16:03
Also proxying would ruin CPU cache-based speedup since it would need to go through a double indirection to access list elements. – Vladimir Matveev Jun 02 '15 at 16:05
if 'T: Copy' then you can only do one allocation when creating the vec, and then afterwards just copy the vec's values over the linked lists's values – oli_obk Jun 02 '15 at 17:13

score 0 · Answer 2 · edited May 23 '17 at 11:55

See this question, its quite similar but not language spesific.

A while ago I investigated this topic (using C, but applies to Rust too).

Besides converting to a vector & sorting, then converting back to a linked list. Merge-sort is typically the best method to sort a linked list.

The same method can be used both for double and single linked lists (there is no advantage to having links in both directions).

Here is an example, originally from this answer, which I ported to C.

This is a nice example of merge-sort, however after some further investigation I found Mono's eglib mergesort to be more efficient, especially when the list is already partially sorted.

Here is a portable version of it.

It shouldn't be too difficult to port this from C to Rust.

How can I sort a LinkedList with just the standard library?

2 Answers2