custom sorting of lists ?

[Steven Schveighoffer]

On 10/13/18 3:48 AM, Jacob Carlborg wrote:
> On 2018-10-12 21:40, Codifies wrote:
>> a while ago I wrote a doubly linked list (in C), which has a compare 
>> callback to allow custom sorting for example
>>
>> int cmpNodes(cnode_t* n1, cnode_t* n2)
>> {
>>    mapNode_t* rn1 = (mapNode_t*)(n1->data);
>>    mapNode_t* rn2 = (mapNode_t*)(n2->data);
>>    if (rn1->G + rn1->H > rn2->G + rn2->H) return 1;
>>    return 0;
>> }
>>
>> would be called by
>>
>> clistSort(openList, cmpNodes);
>>
>> The list would then be ordered by G + H fields (or any other algorithm 
>> you code)
>>
>>
>> I notice there is a doubly linked list in the standard library, 
>> however it doesn't seem to allow for a custom compare, I'd rather not 
>> port my old C list code, can someone please give me some clues as to 
>> how I can reorder a list with a custom comparison...?
> 
> I don't think you can sort a list because sorting requires random 
> access, which a list doesn't provide. Is there a reason you cannot use 
> an array?
> 

You can't quick-sort a list. You can merge sort it, and it's O(nlgn).

I'll work on getting a sort routine into Phobos for it, but I don't know 
what the appropriate location for it is, as a member or along-side 
std.algorithm.sort.

-Steve