Merge sort on Linked List

Z

Zeba

Hi,

I have to write program in C# to merge sort a linked list (doubly
linked). Is it true that the best way to do it is copy it into an
array, sort it and then convert back ?

I'm new to C#, but I tried to develop a merge sort program myself, but
have got stuck with a Null reference exception for the pos variable in
merge function. Also I wrote a function to get the actual nodes from
teh index values before calling merge function. Is there a more
efficient way of doing it ? Please help me !

The code I wrote is as below :

using System;
using System.Collections.Generic;

namespace MergeSort_LL_2
{
class myclass2
{

public static void Main()
{
LinkedList<int> myLL = new LinkedList<int>();

for (int i = 0; i < 15; i++)
for (int j = 15; j > 0; j--)
myLL.AddLast(i * j + 1);
MergeSort(myLL);

foreach (int elt in myLL)
Console.WriteLine(elt);
}


public static void MergeSort(LinkedList<int> myLL)
{
int n = (myLL.Count - 1) / 2;
LinkedListNode<int> myMiddle = myLL.First;
while ((n--)!=0) myMiddle = myMiddle.Next;

msort(myLL, 0, myLL.Count);
}


private static LinkedListNode<int> getNode(LinkedListNode<int>
node, int nodePos)
{
while ((nodePos--) != 0) node = node.Next;
return node;
}

private static void msort(LinkedList<int> myLL, int left, int
right)
{
int mid;
LinkedListNode<int> nLeft, nRight, nMidR;

if (right > left)
{
mid = (right + left) / 2;
msort(myLL, left, mid);
msort(myLL, mid + 1, right);

nLeft = getNode(myLL.First, left);
nMidR = getNode(myLL.First, mid);
nRight = getNode(myLL.First, right);

merge(nLeft, nMidR, nRight);
}
}

private static void merge(LinkedListNode<int> left,
LinkedListNode<int> midR, LinkedListNode<int> right)
{
LinkedListNode<int> midL, pos;
LinkedList<int> result = new LinkedList<int>() ;

LinkedListNode<int> temp = left;

midL = midR.Previous;
pos = result.First;

while ((left != midL) && (midR != right))
{
if ((left.Value <= midR.Value))
{
if (left.Value != null)
{
pos.Value = left.Value;
pos = pos.Next;
left = left.Next;
}
}
else
{
pos.Value = midR.Value;
pos = pos.Next;
midR = midR.Next;
}
}

while (left != midL)
{
pos.Value = left.Value;
left = left.Next;
pos = pos.Next;
}

while (midR != right)
{
pos.Value = midR.Value;
midR = midR.Next;
pos = pos.Next;
}

foreach(int value in result)
{
temp.Value = value;
}
}
}
}
 
Z

Zeba

Well, that's going to be the *easiest* way, but it's not the best way.

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

for a description on how to do it.
Click to expand...

Thanks for all the help ...! I had actually tried out my pgm starting
off with this algorithm. Can you tell me why exactly I'm getting a
null reference exception for pos variable ? Its some mistake in the
merge function I believe...

private static void merge(LinkedListNode<int> left,
LinkedListNode<int> midR, LinkedListNode<int> right)
{
LinkedListNode<int> midL, pos;
LinkedList<int> result = new LinkedList<int>() ;

LinkedListNode<int> temp = left;

midL = midR.Previous;
pos = result.First;

while ((left != midL) && (midR != right))
{
if ((left.Value <= midR.Value))
{
if (left.Value != null)
{
pos.Value = left.Value;
pos = pos.Next;
left = left.Next;
}
}
else
{
 
J

Jon Skeet [C# MVP]

Zeba said:
Thanks for all the help ...! I had actually tried out my pgm starting
off with this algorithm. Can you tell me why exactly I'm getting a
null reference exception for pos variable ? Its some mistake in the
merge function I believe...
Click to expand...

It's impossible to tell without seeing how the lists are set up.

Could you post a short but complete program which demonstrates the
problem?

See http://www.pobox.com/~skeet/csharp/complete.html for details of
what I mean by that.
 
A

Adam Clauss

Zeba said:
Can you tell me why exactly I'm getting a
null reference exception for pos variable ? Its some mistake in the
merge function I believe...
Click to expand...
LinkedList<int> result = new LinkedList<int>() ;
pos = result.First;
Click to expand...

You create result as a new (and empty) list. So, result has NO "First"
element, thus pos is getting set to null.
 
Z

Zeba

You create result as a new (and empty) list. So, result has NO "First"
element, thus pos is getting set to null.
Click to expand...

Okay..Thanks a lot ! Iv got my program up n running after
modifications...
 
Top