Merge sort on Linked List

[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<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;
}
}
}
}

[Peter Bradley]

Isn't that a reinvention of a circular tyred and spoked transportation
object?

Does this help:

http://msdn2.microsoft.com/en-us/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;
}
}
}
}

[Jon Skeet [C# MVP]]

Zeba <co******@gmail.comwrote:

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.

See
http://www.chiark.greenend.org.uk/~s.../listsort.html

for a description on how to do it.

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

[Zeba]

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
{

[Jon Skeet [C# MVP]]

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

[Adam Clauss]

"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

[Zeba]

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...

[Zeba]

Seehttp://www.pobox.com/~skeet/csharp/complete.htmlfor details of

what I mean by that.
--
Jon Skeet - <[e-mail]>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