Originally Posted by seanl1

I suppose it's a right of passage to earn the degree.

Originally Posted by subtercosm

Good. Visual Studio 2008 uses C# 3.0, the latest version.

So suppose you have a linked list type defined by Node:

Help with Code Tags

C# Syntax (Toggle Plain Text)

class Node<T> {
    public T Value { get; set; }
    public Node<T> Tail { get; set; }
}

class Node<T> { public T Value { get; set; } public Node<T> Tail { get; set; } }

The question is: How would we implement a naive, in-place merge sort?

You'd probably want separate functions that implement parts of the merge sort algorithm:

Help with Code Tags

C# Syntax (Toggle Plain Text)

// cuts a list into equal halves
static void CutInHalf(Node<T> list, out Node<T> headOfLastHalf);
 
// merges two sorted lists into a single sorted list, returning the
// reference of the head of the sorted list (which will either be
// the head of a or the head of b)
static Node<T> Merge(Node<T> a, Node<T> b);

// cuts a list into equal halves static void CutInHalf(Node<T> list, out Node<T> headOfLastHalf); // merges two sorted lists into a single sorted list, returning the // reference of the head of the sorted list (which will either be // the head of a or the head of b) static Node<T> Merge(Node<T> a, Node<T> b);

So implement those functions and combine them into the traditional merge sort algorithm.

Any questions?

How much experience do you have with linked lists? Can you do something simple, like reversing a linked list in place?