Sorting a linked list

Question

I have written a basic linked list class in C#. It has a Node object, which (obviously) represents every node in the list.

The code does not use IEnumerable, however, can I implement a sorting function? The language I am using is C#. Is there an example of this in C#?

I am working from this sample:

Thanks

Answer 1

Some people (including me) may have wanted to sort LinkedList<T> from .net library.

The easy way is to use Linq, sort and finally create a new linked list. but this creates garbage. for small collections it would not be a problem, but for large collections it may not be so efficient.

for people who want some degree of optimization, here is generic In-place quick sort implementation for .net doubly linked list.

this implementation does not split/merge, instead it checks nodes for boundaries of each recursion.

/// <summary>
/// in place linked list sort using quick sort.
/// </summary>
public static void QuickSort<T>(this LinkedList<T> linkedList, IComparer<T> comparer)
{
    if (linkedList == null || linkedList.Count <= 1) return; // there is nothing to sort
    SortImpl(linkedList.First, linkedList.Last, comparer);
}

private static void SortImpl<T>(LinkedListNode<T> head, LinkedListNode<T> tail, IComparer<T> comparer)
{
    if (head == tail) return; // there is nothing to sort

    void Swap(LinkedListNode<T> a, LinkedListNode<T> b)
    {
        var tmp = a.Value;
        a.Value = b.Value;
        b.Value = tmp;
    }

    var pivot = tail;
    var node = head;
    while (node.Next != pivot)
    {
        if (comparer.Compare(node.Value, pivot.Value) > 0)
        {
            Swap(pivot, pivot.Previous);
            Swap(node, pivot);
            pivot = pivot.Previous; // move pivot backward
        }
        else node = node.Next; // move node forward
    }
    if (comparer.Compare(node.Value, pivot.Value) > 0)
    {
        Swap(node, pivot);
        pivot = node;
    }

    // pivot location is found, now sort nodes below and above pivot.
    // if head or tail is equal to pivot we reached boundaries and we should stop recursion.
    if (head != pivot) SortImpl(head, pivot.Previous, comparer);
    if (tail != pivot) SortImpl(pivot.Next, tail, comparer);
}

Answer 2

The simplest option is probably to extract the data, sort it in a mechanism that already supports sorting (arrays, List<T> or IEnumerable<T> via LINQ), and re-build the linked list with the sorted data.

If you want to write your own sort algorithm, then you may find Comparer<T>.Default useful (assuming you are using generics). This should allow you to compare any items that are IComparable<T> or IComparable.

As an aside - note that .NET already includes LinkedList<T> etc; if this is just for learning etc, then fine ;-p