P: n/a

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<intmyLL = 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<intmyLL)
{
int n = (myLL.Count  1) / 2;
LinkedListNode<intmyMiddle = myLL.First;
while ((n)!=0) myMiddle = myMiddle.Next;
msort(myLL, 0, myLL.Count);
}
private static LinkedListNode<intgetNode(LinkedListNode<int>
node, int nodePos)
{
while ((nodePos) != 0) node = node.Next;
return node;
}
private static void msort(LinkedList<intmyLL, int left, int
right)
{
int mid;
LinkedListNode<intnLeft, 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<intleft,
LinkedListNode<intmidR, LinkedListNode<intright)
{
LinkedListNode<intmidL, pos;
LinkedList<intresult = new LinkedList<int>() ;
LinkedListNode<inttemp = 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;
}
}
}
}  
Share this Question
P: n/a

Isn't that a reinvention of a circular tyred and spoked transportation
object?
Does this help: http://msdn2.microsoft.com/enus/library/5z658b67.aspx
Peter
"Zeba" <co******@gmail.comwrote in message
news:11**********************@p10g2000cwp.googlegr oups.com...
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<intmyLL = 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<intmyLL)
{
int n = (myLL.Count  1) / 2;
LinkedListNode<intmyMiddle = myLL.First;
while ((n)!=0) myMiddle = myMiddle.Next;
msort(myLL, 0, myLL.Count);
}
private static LinkedListNode<intgetNode(LinkedListNode<int>
node, int nodePos)
{
while ((nodePos) != 0) node = node.Next;
return node;
}
private static void msort(LinkedList<intmyLL, int left, int
right)
{
int mid;
LinkedListNode<intnLeft, 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<intleft,
LinkedListNode<intmidR, LinkedListNode<intright)
{
LinkedListNode<intmidL, pos;
LinkedList<intresult = new LinkedList<int>() ;
LinkedListNode<inttemp = 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;
}
}
}
}  
P: n/a

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 ?
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.
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<intleft,
LinkedListNode<intmidR, LinkedListNode<intright)
{
LinkedListNode<intmidL, pos;
LinkedList<intresult = new LinkedList<int>() ;
LinkedListNode<inttemp = 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
{  
P: n/a

Zeba <co******@gmail.comwrote:
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...
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.

Jon Skeet  <sk***@pobox.com> http://www.pobox.com/~skeet Blog: http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too  
P: n/a

"Zeba" <co******@gmail.comwrote in message
news:11**********************@t69g2000cwt.googlegr oups.com...
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...
LinkedList<intresult = new LinkedList<int>() ;
pos = result.First;
You create result as a new (and empty) list. So, result has NO "First"
element, thus pos is getting set to null.

Adam Clauss  
P: n/a

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

Adam Clauss
Okay..Thanks a lot ! Iv got my program up n running after
modifications...  
P: n/a

Seehttp://www.pobox.com/~skeet/csharp/complete.htmlfor details of
what I mean by that.

Jon Skeet  <s...@pobox.com>http://www.pobox.com/~skeet Blog:http://www.msmvps.com/jon.skeet
If replying to the group, please do not mail me too
Thanks, that was informative. I'm new to discussion forums..so it was
helpful
Zeba Ahmad   This discussion thread is closed Replies have been disabled for this discussion.   Question stats  viewed: 13243
 replies: 7
 date asked: Feb 16 '07
