Trouble in implementing link list sorting in c#

Question

I am having trouble implementing a sort algo (merge) for singly list as defined below My mergesort method always gives me null..I am not able to figure out what is wrong Can you guys help me out?

Node class

public class Node
        {
           private int data;
           private  Node next;
    }

Linked List class

public class SSL
        {
            private Node head;
    }

My merge sort code

public static void MergeSort(SSL a)
        {
            SSL x = new SSL();
            SSL y = new SSL();
            if (a.Head == null || a.Head.Next == null) // base case if list has 0 or 1 element
                return;
            AlternateSplitting(a, x, y);
            MergeSort(x);
            MergeSort(y);
            a = SortedMerge(x, y);
        }

I implemented following helper methods to implement merge sort

AlternateSplitting: This method will split the list into 2 lists

public static void AlternateSplitting(SSL src, SSL odd, SSL even)
        {

            while (src.Head != null)
            {
                MoveNode(odd, src);
                if (src.Head != null)
                    MoveNode(even, src);
            }


        } // end of AlternateSplitting

This method will merge the 2 list and return a new list

public static SSL SortedMerge(SSL a, SSL b)
        {
            SSL c = new SSL();
            if (a.Head == null)
                return b;
            else
                if (b.Head == null)
                    return a;
                else
                {
                    bool flagA = false;
                    bool flagB = false;
                    Node currentA = new Node();
                    Node currentB = new Node();

                    while (!flagA && !flagB)
                    {
                        currentA = a.Head;
                        currentB = b.Head;
                        if (currentA.Data < currentB.Data)
                        {
                            MoveNodeToEnd(a, c);
                            currentA = a.Head;
                            if (currentA== null)
                                flagA = true;
                        }
                        else
                            if (currentA.Data > currentB.Data)
                            {
                                MoveNodeToEnd(b, c);
                                currentB = b.Head;
                                if (currentB== null)
                                    flagB = true;

                            }
                    } // end of while

                    if (flagA)
                    {

                        while (currentB != null)
                        {
                            MoveNodeToEnd(b, c);
                            currentB = b.Head;
                        }

                    }
                    else
                        if(flagB)
                        {

                            while (currentA != null)
                            {
                                MoveNodeToEnd(a, c);
                                currentA = a.Head;
                            }

                        }
                    return c;


                } // end of outer else

        } // end of function sorted merge

Answer 1

I am not able to figure out what is wrong Can you guys help me out?

Find a bug and you fix it for a day. Teach how to find bugs and believe me, it takes a lifetime to fix the bugs. :-)

Your fundamental problem is not that the algorithm is wrong -- though, since it gives incorect results, it certainly is wrong. But that's not the fundamental problem. The fundamental problem is that you don't know how to figure out where a program goes wrong. Fix that problem first! Learn how to debug programs.

Being able to spot the defect in a program is an acquired skill like any other -- you've got to learn the basics and then practice for hundreds of hours. So learn the basics.

Start by becoming familiar with the basic functions of your debugger. Make sure that you can step through programs, set breakpoints, examine local variables, and so on.

Then write yourself some debugging tools. They can be slow -- you're only going to use them when debugging. You don't want your debugging tools in the production version of your code.

The first debugging tool I would write is a method that takes a particular Node and produces a comma-separated list of the integers that are in the list starting from that node. So you'd say DumpNode(currentB) and what would come back is, say "{10,20,50,30}". Obviously doing the same for SSL is trivial if you can do it for nodes.

I would also write tools that do things like count nodes in a list, tell you whether a given list is already sorted, and so on.

Now you have something you can type into the watch window to more easily observe the changes to your data structures as they flow by. (There are ways to make the debugger do this rendering automatically, but we're discussing the basics here, so let's keep it simple.)

That will help you understand the flow of data through the program more easily. And that might be enough to find the problem. But maybe not. The best bugs are the ones that identify themselves to you, by waving a big red flag that says "there's a bug over here". The tool that turns hard-to-find bugs into self-identifying bugs is the debug assertion.

When you're writing your algorithm, think "what must be true?" at various points. For example, before AlternateSplitting runs, suppose the list has 10 items. When it is done running, the two resulting lists had better have 5 items each. If they don't, if they have 10 items each or 0 items each or one has 3 and the other has 7, clearly you have a bug somewhere in there. So start writing debug-only code:

public static void AlternateSplitting(SSL src, SSL odd, SSL even)        
{
#if DEBUG
  int srcCount = CountList(src);
#endif
  while (src.Head != null) { blah blah blah }
#if DEBUG
  int oddCount = CountList(odd);
  int evenCount = CountList(even);
  Debug.Assert(CountList(src) == 0);
  Debug.Assert(oddCount + evenCount == srcCount);
  Debug.Assert(oddCount == evenCount || oddCount == evenCount + 1);
#endif
}

Now AlternateSplitting will do work for you in the debug build to detect bugs in itself. If your bug is because the split is not working out correctly, you'll know immediately when you run it.

Do the same thing to the list merging algorithm -- figure out every point where "I know that X must be true at this point", and then write a Debug.Assert(X) at that point. Then run your test cases. If you have a bug, then the program will tell you and the debugger will take you right to it.

Good luck!