Linked List Sorting Algorithm I was working on a sorting algorithm for my linked list implementation and wanted to get other people's input/comments/critique. What do you think of it in all aspects, including style?

I was told that it is preferred to use a bool type for the changeFlag instead of using an int as it makes it more readable.  Thoughts?

void LinkedList::sort()
{
    if (head != 0)
    {
        Node* current = head;
        Node* prev = 0;
        Node* tempNode = 0;
        bool changeFlag = false;
        for (int i = 0; i &lt; length; i++)
        {
            while (current-&gt;next != 0)
            {
                tempNode = current-&gt;next;

                if (current-&gt;value &gt; tempNode-&gt;value)
                {
                    changeFlag = true;
                    current-&gt;next = tempNode-&gt;next;
                    tempNode-&gt;next = current;
                    if (prev != 0)
                        prev-&gt;next = tempNode;
                    prev = tempNode;
                    if (head == current)
                        head = tempNode;
                    if (current-&gt;next == 0)
                        end = current;
                }
                else
                {
                    prev = current;
                    current = current-&gt;next;
                }
            }
            if (changeFlag == false)
                break;
            else
            {
                prev = 0;
                current = head;
                changeFlag = false;
            }
        }
    }
}
What I would take away from this is how the standard library does this.

It disassociates sorting algorithms from specific container types (by using iterators). Then you can write the sorting algorithm in a way that is independent of the actual container type.

What I dislike about your code is that when you move elements you basically re-order the list (you actually move the nodes). This is a complex operation taking many checks. Personally I would leave the actual nodes where they are and move the values between nodes. std::swap() can be used for this.

This:

               current-&gt;next = tempNode-&gt;next;
                tempNode-&gt;next = current;
                if (prev != 0)
                    prev-&gt;next = tempNode;
                prev = tempNode;
                if (head == current)
                    head = tempNode;
                if (current-&gt;next == 0)
                    end = current;


Can be replaced with:

                swap(current-&gt;value, tempNode-&gt;value);


With C++ new move semantics this is now very efficient.


  EDIT: I was told that it is preferred to use a bool type for the changeFlag instead of using an int as it makes it more readable?? Thoughts?


Yes. Use the correct type. bool is a truth value it imparts meaning to the person reading the code. Humans need that extra meaning to help them understand the code better.