How should I sort a doubly linked list the D way?

[Jonathan M Davis]

On Tuesday, August 13, 2019 3:48:52 AM MDT Mirjam Akkersdijk via 
Digitalmars-d-learn wrote:
> Hello there,
> If I had a DLL, how would I sort it judging by the node contents,
> the D way?
>
> In C if I were to sort a piece of malloc'd memory pointing to
> node pointers, I would write my compare function and let qsort
> sort it out. In D, I tried to use std.algorithm's sort
> functionality to no avail, because my guess would be it only
> operates on arrays. This opens up another can of worms as I am
> not fond of VLAs and D desperately wants to know what the size is
> at compile time.
>
> Let's say we this trivial implementation:
>
> Node* get_node(DLL* list, uint index);
>
> struct Node {
>    int x;
>    Node* prev, next;
> };
>
> struct DLL {
>    Node* head;
>    uint size;
> };
>
> Node** nodes = cast(Node**) malloc(DLL.size * (Node*).sizeof);
>
> and I would like to sort based on Node.t, how should I tackle it,
> preferably without resorting to C libraries?

std.algorithm.sort operates on random-access ranges, not just dynamic
arrays, and there's no need to know the size at compile time. I don't know
why you would think that arrays would need to know their size at compile
time unless you've only been using static arrays. However, a doubly-linked
list definitely isn't random access, so it wouldn't work with
std.algorithm.sort, and I don't think that Phobos has anything which would
be able to sort it. There might be a solution somewhere on code.dlang.org,
but I don't know of any that I could point you to. Either way, if there's a
solution floating around that you can use to sort a doubly-linked list in
place, it's not an official one.

- Jonathan M Davis