How to sort a doubly linked list SplDoublyLinkedList?

Question

PHP

I have a doubly linked list that I need to sort in O(n Log n) time. I'd like to use merge sort, but I can't figure out how to implement this by extending the SplDoublyLinkedList class from the PHP standard library.
The main problem is that I can't split the SplDoublyLinkedList in half without allocating more memory. If I had individual node objects, I could easily set the node's next pointer from the middle of the list to null, and store the pointer to the next node in a separate variable, thus getting two linked lists already. But SplDoublyLinkedList does not allow you to perform such an operation.
I mean something similar in Java:

node mergeSort(node h) 
    { 
        if (h == null || h.next == null) { 
            return h; 
        } 

        node middle = getMiddle(h); 
        node nextOfMiddle = middle.next; 

        middle.next = null; 

        node left = mergeSort(h); 
        node right = mergeSort(nextofmiddle); 

        node sortedlist = sortedMerge(left, right); 
        return sortedlist; 
    }

Should I really use SplDoublyLinkedList in this case, or am I better off writing my own linked list implementation?

Answer 1

If there is no way to access the element by index, it will not be possible to keep within O(n Log n).
Because the list can only be traversed sequentially (sorting through all the elements to the desired one), and not arbitrarily.
Maybe it's easier to add elements to the list so that they are sorted?

Answer 2

It turns out a little in one place, but since you need it in php, before also with SplDoublyLinkedList, then ...
You can, instead of one operation of splitting the list, simply bite off the element from the end in a loop using pop and add it to another list using push .
This will not affect n log n complexity. It will just slow down exactly 1.5-2 times, depending on the implementation of merge.