Performing MergeSort on a singly linked list

[seanl1]

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.

http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html

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

[subtercosm]

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.

Here is a partial answer:

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.

[seanl1]

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.

[subtercosm]

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

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

[seanl1]

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

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

That's an excellent explanation. Thank you very much. I have as much experience with linked lists and one would expect a month into Data Structures I. However, I can reverse linked lists, iterate through them, I understand the concept of pointers, nodes, etc. Certainly enough to understand your code snippet.