How can I sort LinkedList with just the standard library?

Question

Vec provides a sorting method (via the Deref implementation), but LinkedList does not. Is there a general algorithm somewhere in the Rust standard library that allows you to sort LinkedList s?

Answer 1

I do not think there is a built-in way to do this. However, you can move the contents of the list to Vec , sort it, and return it back to the linked list:

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

This idea is not as far away as it might seem - see here . While relatively fast linked list sorting algorithms exist, they won’t give you as much cache performance as sorting flat arrays.

Answer 2

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

---

Some time ago I researched this topic (using C, but also applies to Rust).

In addition to converting to vector and sorting, then converting back to a linked list. Merge-sort is usually the best method for sorting a linked list.

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

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

This is a good example of merge-sort, but after some further research, I found Mono eglib mergesort more efficient, especially when the list is already partially sorted.

Here is the portable version .

It's not too complicated to port this from C to Rust.