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

[Jonathan M Davis]

On Tuesday, August 13, 2019 11:33:10 AM MDT Mirjam Akkersdijk via 
Digitalmars-d-learn wrote:
> On Tuesday, 13 August 2019 at 14:04:45 UTC, Sebastiaan Koppe
>
> wrote:
> > On Tuesday, 13 August 2019 at 09:48:52 UTC, Mirjam Akkersdijk
> >
> > wrote:
> >> and I would like to sort based on Node.t, how should I tackle
> >> it, preferably without resorting to C libraries?
> >
> > Convert the nodes into an D array, sort the array with
> > nodes.sort!"a.x < b.x" and then iterate the array and repair
> > the next/prev pointers.
>
> Thank you, this is what I eventually chose to do. It's also
> fairly fast, though doesn't the nature of the dynamic array slow
> it down a bit? Since I already know the size of the array (but
> just not at compile time), can't I define an array of fixed size,
> which is dependent on the input of the function?

In D, static arrays must know their length at compile time. Dynamic arrays
can have their length determined at runtime. I don't know why a dynamic
array would slow anything down here though - especially if you just allocate
it with the correct length. Appending each element individually instead of
allocating the full dynamic array and then setting each element would
certainly be slower, but once the dynamic array is fully allocated, as far
as accessing elements go, accessing a dynamic array and static array should
be basically the same. The only real difference is that one would have its
elements on the stack, whereas the other would have them on the heap. Even
if you used a static array, you'd have to slice it to pass to sort, which
would mean that you'd be passing it a dynamic array. A dynamic array is
basically just a struct with a pointer and a length. e.g.

struct DynamicArray(T)
{
    size_t length;
    T* ptr;
}

and accessing its elements is the same as you'd get with a pointer in C
except for the fact that in @safe code, the bounds are checked when indexing
elements. The only thing about dynamic arrays that can get slow is if you're
doing a lot of appending to them, because then it has to keep checking to
see whether it can expand in place or has to allocate a new block of memory
and copy the elements. In that respect, it's similar to C++'s std::vector.

- Jonathan M Davis