Re: Merge sort on Linked List

Tech-Archive recommends: Repair Windows Errors & Optimize Windows Performance

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" <coolzebs@xxxxxxxxx> wrote in message
news:1171629065.436324.120660@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
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;
}
}
}
}



.

Relevant Pages