Alright guys, I'm in a Data Structures I class which is proving to be impossible at some junctures. I suppose it's a right of passage to earn the degree. I know how mergesort works on Arrays, but our professor has purposely used the linked list data structure to up the difficulty. Through Google, I think I've found a great resource to help me out a bit.

If you guys could help explain it in terms of C# it'd go a long way in helping me solve this problem. Thanks.

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

You mean a rite of passage. Also, it's the most important or second-most important class you'll take.

What version of C# are you familiar with? If you answer in the next few minutes, I'll tailor my answer to `Math.Max(2.0, version)` where `version` is the version you reply with.

Also, if it is important, specify whether you want to work with doubly-linked linked lists or singly-linked. If you have no preference, I will go with singly-linked.

The one feature of a linked list merge sort is that you can sort the list in place -- the only pieces of the nodes that you modify are the references between nodes. The basic algorithm for merge sort is the same: cut the list in two, sort the parts, and merge them back together. It's hard to understand the source of your confusion -- one might be confusion with linked lists in general, another might be confusion about the algorithm I just described.

Excuse my grammar, I did mean "rite" of passage. As far as what version I'm using, I know I'm using Microsoft C# Express 2008. Also, we're working with Singly Linked lists.

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

``````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:

``````// 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
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?

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

``````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:

``````// 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