using System;

public class Program

{

    public static void Main()

    {

        Node<int> head = FormLinkedListNodesForInsertionSort();

        Print(head, "Original List before Sorting: ");

        Console.WriteLine("");Console.WriteLine("");

        Node<int> sorted = InsertionSort(head);

        Print(sorted, "After Sorting: ");

    }

    private static void Print(Node<int> node, string str)

    {

     Console.Write(str);

     while(node != null)

     {

      Console.Write(node.data + " --> ");

      node = node.next;

     }

     Console.Write("null");

    }

    private static Node<int> FormLinkedListNodesForInsertionSort()

    {

        Node<int> node = new Node<int>();

        node.data = 6;

        node.next = new Node<int>();

        node.next.data = 5;

        node.next.next = new Node<int>();

        node.next.next.data = 3;

        node.next.next.next = new Node<int>();

        node.next.next.next.data = 1;

        node.next.next.next.next = new Node<int>();

        node.next.next.next.next.data = 8;

        node.next.next.next.next.next = new Node<int>();

        node.next.next.next.next.next.data = 7;

        node.next.next.next.next.next.next = new Node<int>();

        node.next.next.next.next.next.next.data = 2;

        node.next.next.next.next.next.next.next = new Node<int>();

        node.next.next.next.next.next.next.next.data = 4;

        node.next.next.next.next.next.next.next.next = null;

        return node;

    }

    // Loop thru every node in the list

    private static Node<int> InsertionSort(Node<int> head)

    {

        Node<int> sorted = null;

        Node<int> current = head;

​

        while (current != null)

        {

            Node<int> next = current.next;

            sorted = SortNodes(current, sorted); // Pass current node to SortNodes method

            current = next;

        }

        return sorted;

    }

​

    //Collect each node and form a sorted list

    // make sure the collected node is added next to the corresponding/sorted element

    private static Node<int> SortNodes(Node<int> newnode, Node<int> sorted)

    {

        if (sorted == null || sorted.data >= newnode.data) // this is for first node or node value less than head of sorted node, so we have to add first

        {

            newnode.next = sorted;

            sorted = newnode;

        }

        else

        {

            Node<int> current = sorted;

            while (current.next != null && current.next.data < newnode.data) // Already sorted, so looping thru

            {

                current = current.next;

            }

            newnode.next = current.next;

            current.next = newnode;

        }

        return sorted; // Every time head of sorted node is returned

    }

}

​

public class Node<T>

{

   public Node<T> next;

   public T data;

   public Node()

   {

   }

​

   public Node(T obj)

   {

    data = obj;

   }

}