How to efficiently sort list of nodes with next and previous node references?

I have a collection of items in random each having the following data structures:

// NOTE: Was "Vertex" in the comments...
public class Item
{
    public string Data { get; set; }
}

public class Node
{
    pu开发者_StackOverflow中文版blic Item Next { get; set; }
    public Item Previous { get; set; }
}

Example:

var a = new Item();
var b = new Item();
var c = new Item();
var d = new Item();

var nodeA = new Node() { Previous = null };
var nodeB = new Node() { Previous = a };
nodeA.Next = b;
var nodeC = new Node() { Previous = b };
nodeB.Next = c;
var nodeD = new Node() { Previous = c, Next = null };
nodeC.Next = d;

// This would be input to the sort method (completely random order).
var items = new []{ nodeC, nodeA, nodeD, nodeB };

// Execute sort

// Result: nodeA, nodeB, nodeC, nodeD.

Obviously a O(n²) solution is possible. However, I would like to sort these in the correct order in less than O(n²). Is this possible?

---

Looking at it... assuming you aren't using circular lists, couldn't you just iterate through your random-order array until you find the starting node (the one with .Previous == null) and then return the node? I mean, one of the advantages of a linked list is that you don't have to store references to all the nodes in a separate data structure, just have them each connected to each other. (Well, depending on how the language implementation you're using does reference counting and garbage collection, if it does them at all.)

But basically, unless you have an immediate need after the operation to access an element a certain distance from the starting node, I'd recommend just immediately returning the starting node when encountered and then lazily assigning to an array of the proper size as you use each successive node. In fact, even if you create a new array and assign to it, wouldn't the worst-time case still just be O(n), with n being the number of nodes? O(n) to find the starting node, and then another O(n) n to iterate through the list, assigning each node to the corresponding index in an array of the same size as your input array.

---

Based on your updated question, it might be a good idea for you to implement a temporary set of linked lists. As you initially iterate through the list, you'd check the Next and Previous elements of each node, and then store the Nexts and Previouses in Dictionary-esque objects (I'm not sure what .NET object would be best suited for that) as keys, with linked-list nodes wrapped around the existing Nodes referencing the Items being the values. That way you'd build up the links as you go along without any actual sorting, and would ultimately just iterate through your temporary list, assigning the Nodes wrapped by the listnodes to a new array to return.

This should be better than O(n^2) due to dictionary accesses generally being constant-time on average (though worst-case asymptotic behavior is still O(n)), I believe.

---

I think merge sort can work. Something like...

  merge_sort_list(list, chain_length)
  1. if chain_length > 1 then
  2.    merge_sort_list(list, chain_length/2)
  3.    middle_node = step_into_by(list, chain_length)
  4.    merge_sort_list(middle, chain_length - chain_length/2)
  5.    merge_list_halves(list, middle, chain_length)

  merge_list_halves(list, middle, chain_length)
  1. ... you get the idea

---

Merge Sort comes to mind... I think this should be applicable here and it performs (worst case) in O(n log n).

Merge sort is often the best choice for sorting a linked list: in this situation it is relatively easy to implement a merge sort in such a way that it requires only Θ(1) extra space, and the slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible.

Edit: after re-reading your question, it doesn't make much sense anymore. Basically you want to sort so that the items are in the order given by the list? That is doable in linear O(n) time: first you travel backwards to the first item in the list (via references) and then you just yield each item forward. Or are your Next/Previous not references?